<!DOCTYPE html><html lang="zh-CN" data-theme="light"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width,initial-scale=1"><title>JDK8 HashMap源码 | Joey</title><meta name="keywords" content="Java,源码,HashMap"><meta name="author" content="方陈勇"><meta name="copyright" content="方陈勇"><meta name="format-detection" content="telephone=no"><meta name="theme-color" content="#ffffff"><meta name="description" content="JDK8 HashMap源码">
<meta property="og:type" content="article">
<meta property="og:title" content="JDK8 HashMap源码">
<meta property="og:url" content="https://fangchenyong.top/2021/03/20/Java-%E6%BA%90%E7%A0%81-JDK8-HashMap/index.html">
<meta property="og:site_name" content="Joey">
<meta property="og:description" content="JDK8 HashMap源码">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://fangchenyong.oss-cn-hangzhou.aliyuncs.com/BEF238F4E59CF4D91A694FE9C5DBC030.JPG">
<meta property="article:published_time" content="2021-03-19T16:00:00.000Z">
<meta property="article:modified_time" content="2021-03-19T16:00:00.000Z">
<meta property="article:author" content="方陈勇">
<meta property="article:tag" content="Java">
<meta property="article:tag" content="源码">
<meta property="article:tag" content="HashMap">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://fangchenyong.oss-cn-hangzhou.aliyuncs.com/BEF238F4E59CF4D91A694FE9C5DBC030.JPG"><link rel="shortcut icon" href="/img/favicon.png"><link rel="canonical" href="https://fangchenyong.top/2021/03/20/Java-%E6%BA%90%E7%A0%81-JDK8-HashMap/"><link rel="preconnect" href="//cdn.jsdelivr.net"/><link rel="stylesheet" href="/css/index.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free/css/all.min.css" media="print" onload="this.media='all'"><script>const GLOBAL_CONFIG = { 
  root: '/',
  algolia: undefined,
  localSearch: undefined,
  translate: undefined,
  noticeOutdate: undefined,
  highlight: {"plugin":"highlighjs","highlightCopy":true,"highlightLang":true,"highlightHeightLimit":false},
  copy: {
    success: '复制成功',
    error: '复制错误',
    noSupport: '浏览器不支持'
  },
  relativeDate: {
    homepage: false,
    post: false
  },
  runtime: '天',
  date_suffix: {
    just: '刚刚',
    min: '分钟前',
    hour: '小时前',
    day: '天前',
    month: '个月前'
  },
  copyright: undefined,
  lightbox: 'fancybox',
  Snackbar: undefined,
  source: {
    jQuery: 'https://cdn.jsdelivr.net/npm/jquery@latest/dist/jquery.min.js',
    justifiedGallery: {
      js: 'https://cdn.jsdelivr.net/npm/justifiedGallery/dist/js/jquery.justifiedGallery.min.js',
      css: 'https://cdn.jsdelivr.net/npm/justifiedGallery/dist/css/justifiedGallery.min.css'
    },
    fancybox: {
      js: 'https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@latest/dist/jquery.fancybox.min.js',
      css: 'https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@latest/dist/jquery.fancybox.min.css'
    }
  },
  isPhotoFigcaption: false,
  islazyload: false,
  isanchor: false
}</script><script id="config-diff">var GLOBAL_CONFIG_SITE = { 
  isPost: true,
  isHome: false,
  isHighlightShrink: false,
  isToc: true,
  postUpdate: '2021-03-20 00:00:00'
}</script><noscript><style type="text/css">
  #nav {
    opacity: 1
  }
  .justified-gallery img {
    opacity: 1
  }

  #recent-posts time,
  #post-meta time {
    display: inline !important
  }
</style></noscript><script>(win=>{
    win.saveToLocal = {
      set: function setWithExpiry(key, value, ttl) {
        if (ttl === 0) return
        const now = new Date()
        const expiryDay = ttl * 86400000
        const item = {
          value: value,
          expiry: now.getTime() + expiryDay,
        }
        localStorage.setItem(key, JSON.stringify(item))
      },

      get: function getWithExpiry(key) {
        const itemStr = localStorage.getItem(key)

        if (!itemStr) {
          return undefined
        }
        const item = JSON.parse(itemStr)
        const now = new Date()

        if (now.getTime() > item.expiry) {
          localStorage.removeItem(key)
          return undefined
        }
        return item.value
      }
    }
  
    win.getScript = url => new Promise((resolve, reject) => {
      const script = document.createElement('script')
      script.src = url
      script.async = true
      script.onerror = reject
      script.onload = script.onreadystatechange = function() {
        const loadState = this.readyState
        if (loadState && loadState !== 'loaded' && loadState !== 'complete') return
        script.onload = script.onreadystatechange = null
        resolve()
      }
      document.head.appendChild(script)
    })
  
      win.activateDarkMode = function () {
        document.documentElement.setAttribute('data-theme', 'dark')
        if (document.querySelector('meta[name="theme-color"]') !== null) {
          document.querySelector('meta[name="theme-color"]').setAttribute('content', '#0d0d0d')
        }
      }
      win.activateLightMode = function () {
        document.documentElement.setAttribute('data-theme', 'light')
        if (document.querySelector('meta[name="theme-color"]') !== null) {
          document.querySelector('meta[name="theme-color"]').setAttribute('content', '#ffffff')
        }
      }
      const t = saveToLocal.get('theme')
    
          if (t === 'dark') activateDarkMode()
          else if (t === 'light') activateLightMode()
        
      const asideStatus = saveToLocal.get('aside-status')
      if (asideStatus !== undefined) {
        if (asideStatus === 'hide') {
          document.documentElement.classList.add('hide-aside')
        } else {
          document.documentElement.classList.remove('hide-aside')
        }
      }
    })(window)</script><meta name="generator" content="Hexo 5.4.0"></head><body><div id="sidebar"><div id="menu-mask"></div><div id="sidebar-menus"><div class="author-avatar"><img class="avatar-img" src="https://fangchenyong.oss-cn-hangzhou.aliyuncs.com/3FD9B055-6361-49B7-B8CE-5BA9144BD27F.JPG" onerror="onerror=null;src='/img/friend_404.gif'" alt="avatar"/></div><div class="site-data"><div class="data-item is-center"><div class="data-item-link"><a href="/archives/"><div class="headline">文章</div><div class="length-num">43</div></a></div></div><div class="data-item is-center"><div class="data-item-link"><a href="/tags/"><div class="headline">标签</div><div class="length-num">51</div></a></div></div><div class="data-item is-center"><div class="data-item-link"><a href="/categories/"><div class="headline">分类</div><div class="length-num">53</div></a></div></div></div><hr/><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> Home</span></a></div><div class="menus_item"><a class="site-page" href="/archives/"><i class="fa-fw fas fa-archive"></i><span> Archives</span></a></div><div class="menus_item"><a class="site-page" href="/tags/"><i class="fa-fw fas fa-tags"></i><span> Tags</span></a></div><div class="menus_item"><a class="site-page" href="/categories/"><i class="fa-fw fas fa-folder-open"></i><span> Categories</span></a></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><i class="fa-fw fas fa-list"></i><span> List</span><i class="fas fa-chevron-down expand"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/music/"><i class="fa-fw fas fa-music"></i><span> Music</span></a></li><li><a class="site-page child" href="/movies/"><i class="fa-fw fas fa-video"></i><span> Movie</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="/link/"><i class="fa-fw fas fa-link"></i><span> Link</span></a></div><div class="menus_item"><a class="site-page" href="/about/"><i class="fa-fw fas fa-heart"></i><span> About</span></a></div></div></div></div><div class="post" id="body-wrap"><header class="post-bg" id="page-header" style="background-image: url('https://fangchenyong.oss-cn-hangzhou.aliyuncs.com/BEF238F4E59CF4D91A694FE9C5DBC030.JPG')"><nav id="nav"><span id="blog_name"><a id="site-name" href="/">Joey</a></span><div id="menus"><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> Home</span></a></div><div class="menus_item"><a class="site-page" href="/archives/"><i class="fa-fw fas fa-archive"></i><span> Archives</span></a></div><div class="menus_item"><a class="site-page" href="/tags/"><i class="fa-fw fas fa-tags"></i><span> Tags</span></a></div><div class="menus_item"><a class="site-page" href="/categories/"><i class="fa-fw fas fa-folder-open"></i><span> Categories</span></a></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><i class="fa-fw fas fa-list"></i><span> List</span><i class="fas fa-chevron-down expand"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/music/"><i class="fa-fw fas fa-music"></i><span> Music</span></a></li><li><a class="site-page child" href="/movies/"><i class="fa-fw fas fa-video"></i><span> Movie</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="/link/"><i class="fa-fw fas fa-link"></i><span> Link</span></a></div><div class="menus_item"><a class="site-page" href="/about/"><i class="fa-fw fas fa-heart"></i><span> About</span></a></div></div><div id="toggle-menu"><a class="site-page"><i class="fas fa-bars fa-fw"></i></a></div></div></nav><div id="post-info"><h1 class="post-title">JDK8 HashMap源码</h1><div id="post-meta"><div class="meta-firstline"><span class="post-meta-date"><i class="far fa-calendar-alt fa-fw post-meta-icon"></i><span class="post-meta-label">发表于</span><time class="post-meta-date-created" datetime="2021-03-19T16:00:00.000Z" title="发表于 2021-03-20 00:00:00">2021-03-20</time><span class="post-meta-separator">|</span><i class="fas fa-history fa-fw post-meta-icon"></i><span class="post-meta-label">更新于</span><time class="post-meta-date-updated" datetime="2021-03-19T16:00:00.000Z" title="更新于 2021-03-20 00:00:00">2021-03-20</time></span><span class="post-meta-categories"><span class="post-meta-separator">|</span><i class="fas fa-inbox fa-fw post-meta-icon"></i><a class="post-meta-categories" href="/categories/Java/">Java</a><i class="fas fa-angle-right post-meta-separator"></i><i class="fas fa-inbox fa-fw post-meta-icon"></i><a class="post-meta-categories" href="/categories/Java/%E6%BA%90%E7%A0%81/">源码</a><i class="fas fa-angle-right post-meta-separator"></i><i class="fas fa-inbox fa-fw post-meta-icon"></i><a class="post-meta-categories" href="/categories/Java/%E6%BA%90%E7%A0%81/HashMap/">HashMap</a></span></div><div class="meta-secondline"><span class="post-meta-separator">|</span><span class="post-meta-wordcount"><i class="far fa-file-word fa-fw post-meta-icon"></i><span class="post-meta-label">字数总计:</span><span class="word-count">12.2k</span><span class="post-meta-separator">|</span><i class="far fa-clock fa-fw post-meta-icon"></i><span class="post-meta-label">阅读时长:</span><span>70分钟</span></span></div></div></div></header><main class="layout" id="content-inner"><div id="post"><article class="post-content" id="article-container"><h1 id="HashMap源码"><a href="#HashMap源码" class="headerlink" title="HashMap源码"></a>HashMap源码</h1><p>未完待续…</p>
<figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">package</span> java.util;</span><br><span class="line"></span><br><span class="line"><span class="keyword">import</span> java.io.IOException;</span><br><span class="line"><span class="keyword">import</span> java.io.InvalidObjectException;</span><br><span class="line"><span class="keyword">import</span> java.io.Serializable;</span><br><span class="line"><span class="keyword">import</span> java.lang.reflect.ParameterizedType;</span><br><span class="line"><span class="keyword">import</span> java.lang.reflect.Type;</span><br><span class="line"><span class="keyword">import</span> java.util.function.BiConsumer;</span><br><span class="line"><span class="keyword">import</span> java.util.function.BiFunction;</span><br><span class="line"><span class="keyword">import</span> java.util.function.Consumer;</span><br><span class="line"><span class="keyword">import</span> java.util.function.Function;</span><br><span class="line"></span><br><span class="line"><span class="comment">//HashMap继承了AbstractMap类，实现了Cloneable和Serializable接口</span></span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">HashMap</span>&lt;<span class="title">K</span>,<span class="title">V</span>&gt; <span class="keyword">extends</span> <span class="title">AbstractMap</span>&lt;<span class="title">K</span>,<span class="title">V</span>&gt;</span></span><br><span class="line"><span class="class">    <span class="keyword">implements</span> <span class="title">Map</span>&lt;<span class="title">K</span>,<span class="title">V</span>&gt;, <span class="title">Cloneable</span>, <span class="title">Serializable</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">long</span> serialVersionUID = <span class="number">362498820763181265L</span>;</span><br><span class="line"></span><br><span class="line">    </span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * The default initial capacity - MUST be a power of two.</span></span><br><span class="line"><span class="comment">     * 初始化默认容量为16，必须为2的次方</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> DEFAULT_INITIAL_CAPACITY = <span class="number">1</span> &lt;&lt; <span class="number">4</span>; <span class="comment">// aka 16</span></span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * The maximum capacity, used if a higher value is implicitly specified</span></span><br><span class="line"><span class="comment">     * by either of the constructors with arguments.</span></span><br><span class="line"><span class="comment">     * MUST be a power of two &lt;= 1&lt;&lt;30.</span></span><br><span class="line"><span class="comment">     * 最大容量为2^30</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> MAXIMUM_CAPACITY = <span class="number">1</span> &lt;&lt; <span class="number">30</span>;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * The load factor used when none specified in constructor.</span></span><br><span class="line"><span class="comment">     * 默认负载因子为0.75</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">float</span> DEFAULT_LOAD_FACTOR = <span class="number">0.75f</span>;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * The bin count threshold for using a tree rather than list for a</span></span><br><span class="line"><span class="comment">     * bin.  Bins are converted to trees when adding an element to a</span></span><br><span class="line"><span class="comment">     * bin with at least this many nodes. The value must be greater</span></span><br><span class="line"><span class="comment">     * than 2 and should be at least 8 to mesh with assumptions in</span></span><br><span class="line"><span class="comment">     * tree removal about conversion back to plain bins upon</span></span><br><span class="line"><span class="comment">     * shrinkage.</span></span><br><span class="line"><span class="comment">     * 链表长度树化的阈值</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> TREEIFY_THRESHOLD = <span class="number">8</span>;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * The bin count threshold for untreeifying a (split) bin during a</span></span><br><span class="line"><span class="comment">     * resize operation. Should be less than TREEIFY_THRESHOLD, and at</span></span><br><span class="line"><span class="comment">     * most 6 to mesh with shrinkage detection under removal.</span></span><br><span class="line"><span class="comment">     * 重新转为链表的阈值</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> UNTREEIFY_THRESHOLD = <span class="number">6</span>;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * The smallest table capacity for which bins may be treeified.</span></span><br><span class="line"><span class="comment">     * (Otherwise the table is resized if too many nodes in a bin.)</span></span><br><span class="line"><span class="comment">     * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts</span></span><br><span class="line"><span class="comment">     * between resizing and treeification thresholds.</span></span><br><span class="line"><span class="comment">     * 树化的条件之一，当最大容量超过64</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> MIN_TREEIFY_CAPACITY = <span class="number">64</span>;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * Basic hash bin node, used for most entries.  (See below for</span></span><br><span class="line"><span class="comment">     * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)</span></span><br><span class="line"><span class="comment">     * Node节点用来存储数据</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">static</span> <span class="class"><span class="keyword">class</span> <span class="title">Node</span>&lt;<span class="title">K</span>,<span class="title">V</span>&gt; <span class="keyword">implements</span> <span class="title">Map</span>.<span class="title">Entry</span>&lt;<span class="title">K</span>,<span class="title">V</span>&gt; </span>&#123;</span><br><span class="line">        <span class="keyword">final</span> <span class="keyword">int</span> hash;<span class="comment">//哈希值</span></span><br><span class="line">        <span class="keyword">final</span> K key;<span class="comment">//键</span></span><br><span class="line">        V value;<span class="comment">//值</span></span><br><span class="line">        Node&lt;K,V&gt; next;<span class="comment">//指向下一个节点</span></span><br><span class="line">		</span><br><span class="line">		<span class="comment">//构造函数</span></span><br><span class="line">        Node(<span class="keyword">int</span> hash, K key, V value, Node&lt;K,V&gt; next) &#123;</span><br><span class="line">            <span class="keyword">this</span>.hash = hash;</span><br><span class="line">            <span class="keyword">this</span>.key = key;</span><br><span class="line">            <span class="keyword">this</span>.value = value;</span><br><span class="line">            <span class="keyword">this</span>.next = next;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">final</span> K <span class="title">getKey</span><span class="params">()</span>        </span>&#123; <span class="keyword">return</span> key; &#125;</span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">final</span> V <span class="title">getValue</span><span class="params">()</span>      </span>&#123; <span class="keyword">return</span> value; &#125;</span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">final</span> String <span class="title">toString</span><span class="params">()</span> </span>&#123; <span class="keyword">return</span> key + <span class="string">&quot;=&quot;</span> + value; &#125;</span><br><span class="line">		</span><br><span class="line">		<span class="comment">//重写hashCode()方法</span></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">final</span> <span class="keyword">int</span> <span class="title">hashCode</span><span class="params">()</span> </span>&#123;</span><br><span class="line">            <span class="keyword">return</span> Objects.hashCode(key) ^ Objects.hashCode(value);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">final</span> V <span class="title">setValue</span><span class="params">(V newValue)</span> </span>&#123;</span><br><span class="line">            V oldValue = value;</span><br><span class="line">            value = newValue;</span><br><span class="line">            <span class="keyword">return</span> oldValue;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">		<span class="comment">//重写equals()方法，判断键值是否都相等</span></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">final</span> <span class="keyword">boolean</span> <span class="title">equals</span><span class="params">(Object o)</span> </span>&#123;</span><br><span class="line">            <span class="keyword">if</span> (o == <span class="keyword">this</span>)</span><br><span class="line">                <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">            <span class="keyword">if</span> (o <span class="keyword">instanceof</span> Map.Entry) &#123;</span><br><span class="line">                Map.Entry&lt;?,?&gt; e = (Map.Entry&lt;?,?&gt;)o;</span><br><span class="line">                <span class="keyword">if</span> (Objects.equals(key, e.getKey()) &amp;&amp;</span><br><span class="line">                    Objects.equals(value, e.getValue()))</span><br><span class="line">                    <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/* ---------------- Static utilities -------------- */</span></span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * Computes key.hashCode() and spreads (XORs) higher bits of hash</span></span><br><span class="line"><span class="comment">     * to lower.  Because the table uses power-of-two masking, sets of</span></span><br><span class="line"><span class="comment">     * hashes that vary only in bits above the current mask will</span></span><br><span class="line"><span class="comment">     * always collide. (Among known examples are sets of Float keys</span></span><br><span class="line"><span class="comment">     * holding consecutive whole numbers in small tables.)  So we</span></span><br><span class="line"><span class="comment">     * apply a transform that spreads the impact of higher bits</span></span><br><span class="line"><span class="comment">     * downward. There is a tradeoff between speed, utility, and</span></span><br><span class="line"><span class="comment">     * quality of bit-spreading. Because many common sets of hashes</span></span><br><span class="line"><span class="comment">     * are already reasonably distributed (so don&#x27;t benefit from</span></span><br><span class="line"><span class="comment">     * spreading), and because we use trees to handle large sets of</span></span><br><span class="line"><span class="comment">     * collisions in bins, we just XOR some shifted bits in the</span></span><br><span class="line"><span class="comment">     * cheapest possible way to reduce systematic lossage, as well as</span></span><br><span class="line"><span class="comment">     * to incorporate impact of the highest bits that would otherwise</span></span><br><span class="line"><span class="comment">     * never be used in index calculations because of table bounds.</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> <span class="title">hash</span><span class="params">(Object key)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> h;</span><br><span class="line">        <span class="comment">/**</span></span><br><span class="line"><span class="comment">         * 1.key==null：如果键等于null，哈希值就等于0</span></span><br><span class="line"><span class="comment">         * 2.key!=null：key的hash值与它右移16位后的值按位异或</span></span><br><span class="line"><span class="comment">         * 例如：</span></span><br><span class="line"><span class="comment">         * h = key.hashCode()  1111 1111 1111 1111 1111 0000 1110 1010</span></span><br><span class="line"><span class="comment">         * 					   ^</span></span><br><span class="line"><span class="comment">         * h &gt;&gt;&gt; 16            0000 0000 0000 0000 1111 1111 1111 1111</span></span><br><span class="line"><span class="comment">         * 返回值               0000 0000 0000 0000 0000 1111 0001 0101</span></span><br><span class="line"><span class="comment">        */</span></span><br><span class="line">        <span class="keyword">return</span> (key == <span class="keyword">null</span>) ? <span class="number">0</span> : (h = key.hashCode()) ^ (h &gt;&gt;&gt; <span class="number">16</span>);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * Returns x&#x27;s Class if it is of the form &quot;class C implements</span></span><br><span class="line"><span class="comment">     * Comparable&lt;C&gt;&quot;, else null.</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">static</span> Class&lt;?&gt; comparableClassFor(Object x) &#123;</span><br><span class="line">        <span class="keyword">if</span> (x <span class="keyword">instanceof</span> Comparable) &#123;</span><br><span class="line">            Class&lt;?&gt; c; Type[] ts, as; Type t; ParameterizedType p;</span><br><span class="line">            <span class="keyword">if</span> ((c = x.getClass()) == String.class) <span class="comment">// bypass checks</span></span><br><span class="line">                <span class="keyword">return</span> c;</span><br><span class="line">            <span class="keyword">if</span> ((ts = c.getGenericInterfaces()) != <span class="keyword">null</span>) &#123;</span><br><span class="line">                <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; ts.length; ++i) &#123;</span><br><span class="line">                    <span class="keyword">if</span> (((t = ts[i]) <span class="keyword">instanceof</span> ParameterizedType) &amp;&amp;</span><br><span class="line">                        ((p = (ParameterizedType)t).getRawType() ==</span><br><span class="line">                         Comparable.class) &amp;&amp;</span><br><span class="line">                        (as = p.getActualTypeArguments()) != <span class="keyword">null</span> &amp;&amp;</span><br><span class="line">                        as.length == <span class="number">1</span> &amp;&amp; as[<span class="number">0</span>] == c) <span class="comment">// type arg is c</span></span><br><span class="line">                        <span class="keyword">return</span> c;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * Returns k.compareTo(x) if x matches kc (k&#x27;s screened comparable</span></span><br><span class="line"><span class="comment">     * class), else 0.</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="meta">@SuppressWarnings(&#123;&quot;rawtypes&quot;,&quot;unchecked&quot;&#125;)</span> <span class="comment">// for cast to Comparable</span></span><br><span class="line">    <span class="function"><span class="keyword">static</span> <span class="keyword">int</span> <span class="title">compareComparables</span><span class="params">(Class&lt;?&gt; kc, Object k, Object x)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> (x == <span class="keyword">null</span> || x.getClass() != kc ? <span class="number">0</span> :</span><br><span class="line">                ((Comparable)k).compareTo(x));</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * Returns a power of two size for the given target capacity.</span></span><br><span class="line"><span class="comment">     * </span></span><br><span class="line"><span class="comment">     * 返回一个大于当前Cap的值，并且这个值要是2的次方</span></span><br><span class="line"><span class="comment">     * 通过按位或的操作将最高位后面的位全变成1，然后最后返回+1，就能得到2的整数次方</span></span><br><span class="line"><span class="comment">     * 那为什么一开始要减1？</span></span><br><span class="line"><span class="comment">     * 为了防止一开始就是2的次方，比如说cap = 8;</span></span><br><span class="line"><span class="comment">     * 1000 | 0100 = 1100</span></span><br><span class="line"><span class="comment">     * 1100 | 0011 = 1111</span></span><br><span class="line"><span class="comment">     * ...</span></span><br><span class="line"><span class="comment">     * n + 1  = 16，返回的值就变成了原来的两倍</span></span><br><span class="line"><span class="comment">     * -1之后</span></span><br><span class="line"><span class="comment">     * 0111 | 0011 = 0100</span></span><br><span class="line"><span class="comment">     * 0100 | 0001 = 0101</span></span><br><span class="line"><span class="comment">     * 0101 | 0000 = 0101</span></span><br><span class="line"><span class="comment">     * ...</span></span><br><span class="line"><span class="comment">     * 0101 = 7 ;返回 7+1 = 8</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">static</span> <span class="keyword">final</span> <span class="keyword">int</span> <span class="title">tableSizeFor</span><span class="params">(<span class="keyword">int</span> cap)</span> </span>&#123;</span><br><span class="line">        <span class="comment">//假如 cap = 10,那n = 9 = 0b1001</span></span><br><span class="line">        <span class="keyword">int</span> n = cap - <span class="number">1</span>;</span><br><span class="line">        <span class="comment">//1001 | 0100 = 1110</span></span><br><span class="line">        n |= n &gt;&gt;&gt; <span class="number">1</span>;</span><br><span class="line">        <span class="comment">//1101 | 0011 = 1111</span></span><br><span class="line">        n |= n &gt;&gt;&gt; <span class="number">2</span>;</span><br><span class="line">        <span class="comment">//1111 | 0000 = 1111</span></span><br><span class="line">        n |= n &gt;&gt;&gt; <span class="number">4</span>;</span><br><span class="line">        <span class="comment">//1111 | 0000 = 1111</span></span><br><span class="line">        n |= n &gt;&gt;&gt; <span class="number">8</span>;</span><br><span class="line">        <span class="comment">//1111 | 0000 = 1111 = 15</span></span><br><span class="line">        n |= n &gt;&gt;&gt; <span class="number">16</span>;</span><br><span class="line">        <span class="comment">//如果n小于0，那最小值就是1；</span></span><br><span class="line">        <span class="comment">//如果大于最大容量，那就等于最大容量</span></span><br><span class="line">        <span class="comment">//否则就等于 n + 1，返回2的整数次方</span></span><br><span class="line">        <span class="keyword">return</span> (n &lt; <span class="number">0</span>) ? <span class="number">1</span> : (n &gt;= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/* ---------------- Fields -------------- */</span></span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * The table, initialized on first use, and resized as</span></span><br><span class="line"><span class="comment">     * necessary. When allocated, length is always a power of two.</span></span><br><span class="line"><span class="comment">     * (We also tolerate length zero in some operations to allow</span></span><br><span class="line"><span class="comment">     * bootstrapping mechanics that are currently not needed.)</span></span><br><span class="line"><span class="comment">     * 存放数据的数组，第一次使用的时候进行初始化</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">transient</span> Node&lt;K,V&gt;[] table;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * Holds cached entrySet(). Note that AbstractMap fields are used</span></span><br><span class="line"><span class="comment">     * for keySet() and values().</span></span><br><span class="line"><span class="comment">     * 键值对缓存</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">transient</span> Set&lt;Map.Entry&lt;K,V&gt;&gt; entrySet;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * The number of key-value mappings contained in this map.</span></span><br><span class="line"><span class="comment">     * table中元素数量</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">transient</span> <span class="keyword">int</span> size;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * The number of times this HashMap has been structurally modified</span></span><br><span class="line"><span class="comment">     * Structural modifications are those that change the number of mappings in</span></span><br><span class="line"><span class="comment">     * the HashMap or otherwise modify its internal structure (e.g.,</span></span><br><span class="line"><span class="comment">     * rehash).  This field is used to make iterators on Collection-views of</span></span><br><span class="line"><span class="comment">     * the HashMap fail-fast.  (See ConcurrentModificationException).</span></span><br><span class="line"><span class="comment">     * 结构的修改次数</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">transient</span> <span class="keyword">int</span> modCount;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * The next size value at which to resize (capacity * load factor).</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@serial</span></span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="comment">// (The javadoc description is true upon serialization.</span></span><br><span class="line">    <span class="comment">// Additionally, if the table array has not been allocated, this</span></span><br><span class="line">    <span class="comment">// field holds the initial array capacity, or zero signifying</span></span><br><span class="line">    <span class="comment">// DEFAULT_INITIAL_CAPACITY.)</span></span><br><span class="line">    <span class="comment">// 下一次扩容的阈值</span></span><br><span class="line">    <span class="keyword">int</span> threshold;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * The load factor for the hash table.</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * 负载因子</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@serial</span></span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">final</span> <span class="keyword">float</span> loadFactor;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/* ---------------- Public operations -------------- */</span></span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * Constructs an empty &lt;tt&gt;HashMap&lt;/tt&gt; with the specified initial</span></span><br><span class="line"><span class="comment">     * capacity and load factor.</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span>  initialCapacity the initial capacity</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span>  loadFactor      the load factor</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@throws</span> IllegalArgumentException if the initial capacity is negative</span></span><br><span class="line"><span class="comment">     *         or the load factor is nonpositive</span></span><br><span class="line"><span class="comment">     * 设置初始化容量，负载因子</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">HashMap</span><span class="params">(<span class="keyword">int</span> initialCapacity, <span class="keyword">float</span> loadFactor)</span> </span>&#123;</span><br><span class="line">        <span class="comment">//如果初始容量小于0，抛出异常</span></span><br><span class="line">        <span class="keyword">if</span> (initialCapacity &lt; <span class="number">0</span>)</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">&quot;Illegal initial capacity: &quot;</span> +</span><br><span class="line">                                               initialCapacity);</span><br><span class="line">		<span class="comment">//如果初始容量大于最大容量，那就等于最大容量。</span></span><br><span class="line">        <span class="keyword">if</span> (initialCapacity &gt; MAXIMUM_CAPACITY)</span><br><span class="line">            initialCapacity = MAXIMUM_CAPACITY;</span><br><span class="line">        <span class="comment">//如果负载因子小于0，或者是非数，抛出异常</span></span><br><span class="line">        <span class="keyword">if</span> (loadFactor &lt;= <span class="number">0</span> || Float.isNaN(loadFactor))</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> IllegalArgumentException(<span class="string">&quot;Illegal load factor: &quot;</span> +</span><br><span class="line">                                               loadFactor);</span><br><span class="line">        <span class="comment">//负载因子赋值</span></span><br><span class="line">        <span class="keyword">this</span>.loadFactor = loadFactor;</span><br><span class="line">        <span class="comment">//默认阈值等于数组容量，调用tableSizeFor方法，传入初始容量，返回大于等于容量的最小2的次方</span></span><br><span class="line">        <span class="keyword">this</span>.threshold = tableSizeFor(initialCapacity);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * Constructs an empty &lt;tt&gt;HashMap&lt;/tt&gt; with the specified initial</span></span><br><span class="line"><span class="comment">     * capacity and the default load factor (0.75).</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span>  initialCapacity the initial capacity.</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@throws</span> IllegalArgumentException if the initial capacity is negative.</span></span><br><span class="line"><span class="comment">     * 设置初始化容量，其余都为默认值</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">HashMap</span><span class="params">(<span class="keyword">int</span> initialCapacity)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">this</span>(initialCapacity, DEFAULT_LOAD_FACTOR);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * Constructs an empty &lt;tt&gt;HashMap&lt;/tt&gt; with the default initial capacity</span></span><br><span class="line"><span class="comment">     * (16) and the default load factor (0.75).</span></span><br><span class="line"><span class="comment">     * 无参构造函数，全部为默认值</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">HashMap</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">this</span>.loadFactor = DEFAULT_LOAD_FACTOR; <span class="comment">// all other fields defaulted</span></span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * Constructs a new &lt;tt&gt;HashMap&lt;/tt&gt; with the same mappings as the</span></span><br><span class="line"><span class="comment">     * specified &lt;tt&gt;Map&lt;/tt&gt;.  The &lt;tt&gt;HashMap&lt;/tt&gt; is created with</span></span><br><span class="line"><span class="comment">     * default load factor (0.75) and an initial capacity sufficient to</span></span><br><span class="line"><span class="comment">     * hold the mappings in the specified &lt;tt&gt;Map&lt;/tt&gt;.</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span>   m the map whose mappings are to be placed in this map</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@throws</span>  NullPointerException if the specified map is null</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">HashMap</span><span class="params">(Map&lt;? extends K, ? extends V&gt; m)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">this</span>.loadFactor = DEFAULT_LOAD_FACTOR;</span><br><span class="line">        putMapEntries(m, <span class="keyword">false</span>);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * Implements Map.putAll and Map constructor</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> m the map</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> evict false when initially constructing this map, else</span></span><br><span class="line"><span class="comment">     * true (relayed to method afterNodeInsertion).</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">final</span> <span class="keyword">void</span> <span class="title">putMapEntries</span><span class="params">(Map&lt;? extends K, ? extends V&gt; m, <span class="keyword">boolean</span> evict)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> s = m.size();</span><br><span class="line">        <span class="keyword">if</span> (s &gt; <span class="number">0</span>) &#123;</span><br><span class="line">            <span class="keyword">if</span> (table == <span class="keyword">null</span>) &#123; <span class="comment">// pre-size</span></span><br><span class="line">                <span class="keyword">float</span> ft = ((<span class="keyword">float</span>)s / loadFactor) + <span class="number">1.0F</span>;</span><br><span class="line">                <span class="keyword">int</span> t = ((ft &lt; (<span class="keyword">float</span>)MAXIMUM_CAPACITY) ?</span><br><span class="line">                         (<span class="keyword">int</span>)ft : MAXIMUM_CAPACITY);</span><br><span class="line">                <span class="keyword">if</span> (t &gt; threshold)</span><br><span class="line">                    threshold = tableSizeFor(t);</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">else</span> <span class="keyword">if</span> (s &gt; threshold)</span><br><span class="line">                resize();</span><br><span class="line">            <span class="keyword">for</span> (Map.Entry&lt;? extends K, ? extends V&gt; e : m.entrySet()) &#123;</span><br><span class="line">                K key = e.getKey();</span><br><span class="line">                V value = e.getValue();</span><br><span class="line">                putVal(hash(key), key, value, <span class="keyword">false</span>, evict);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * Returns the number of key-value mappings in this map.</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span> the number of key-value mappings in this map</span></span><br><span class="line"><span class="comment">     * 返回map中键值对的数量</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">size</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> size;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * Returns &lt;tt&gt;true&lt;/tt&gt; if this map contains no key-value mappings.</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span> &lt;tt&gt;true&lt;/tt&gt; if this map contains no key-value mappings</span></span><br><span class="line"><span class="comment">     * 判断是否为空，只需要判断size的大小</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isEmpty</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> size == <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * Returns the value to which the specified key is mapped,</span></span><br><span class="line"><span class="comment">     * or &#123;<span class="doctag">@code</span> null&#125; if this map contains no mapping for the key.</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * &lt;p&gt;More formally, if this map contains a mapping from a key</span></span><br><span class="line"><span class="comment">     * &#123;<span class="doctag">@code</span> k&#125; to a value &#123;<span class="doctag">@code</span> v&#125; such that &#123;<span class="doctag">@code</span> (key==null ? k==null :</span></span><br><span class="line"><span class="comment">     * key.equals(k))&#125;, then this method returns &#123;<span class="doctag">@code</span> v&#125;; otherwise</span></span><br><span class="line"><span class="comment">     * it returns &#123;<span class="doctag">@code</span> null&#125;.  (There can be at most one such mapping.)</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * &lt;p&gt;A return value of &#123;<span class="doctag">@code</span> null&#125; does not &lt;i&gt;necessarily&lt;/i&gt;</span></span><br><span class="line"><span class="comment">     * indicate that the map contains no mapping for the key; it&#x27;s also</span></span><br><span class="line"><span class="comment">     * possible that the map explicitly maps the key to &#123;<span class="doctag">@code</span> null&#125;.</span></span><br><span class="line"><span class="comment">     * The &#123;<span class="doctag">@link</span> #containsKey containsKey&#125; operation may be used to</span></span><br><span class="line"><span class="comment">     * distinguish these two cases.</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@see</span> #put(Object, Object)</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> V <span class="title">get</span><span class="params">(Object key)</span> </span>&#123;</span><br><span class="line">        Node&lt;K,V&gt; e;</span><br><span class="line">        <span class="keyword">return</span> (e = getNode(hash(key), key)) == <span class="keyword">null</span> ? <span class="keyword">null</span> : e.value;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * Implements Map.get and related methods</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> hash hash for key</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> key the key</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span> the node, or null if none</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">final</span> Node&lt;K,V&gt; <span class="title">getNode</span><span class="params">(<span class="keyword">int</span> hash, Object key)</span> </span>&#123;</span><br><span class="line">        Node&lt;K,V&gt;[] tab; Node&lt;K,V&gt; first, e; <span class="keyword">int</span> n; K k;</span><br><span class="line">        <span class="keyword">if</span> ((tab = table) != <span class="keyword">null</span> &amp;&amp; (n = tab.length) &gt; <span class="number">0</span> &amp;&amp;</span><br><span class="line">            (first = tab[(n - <span class="number">1</span>) &amp; hash]) != <span class="keyword">null</span>) &#123;</span><br><span class="line">            <span class="keyword">if</span> (first.hash == hash &amp;&amp; <span class="comment">// always check first node</span></span><br><span class="line">                ((k = first.key) == key || (key != <span class="keyword">null</span> &amp;&amp; key.equals(k))))</span><br><span class="line">                <span class="keyword">return</span> first;</span><br><span class="line">            <span class="keyword">if</span> ((e = first.next) != <span class="keyword">null</span>) &#123;</span><br><span class="line">                <span class="keyword">if</span> (first <span class="keyword">instanceof</span> TreeNode)</span><br><span class="line">                    <span class="keyword">return</span> ((TreeNode&lt;K,V&gt;)first).getTreeNode(hash, key);</span><br><span class="line">                <span class="keyword">do</span> &#123;</span><br><span class="line">                    <span class="keyword">if</span> (e.hash == hash &amp;&amp;</span><br><span class="line">                        ((k = e.key) == key || (key != <span class="keyword">null</span> &amp;&amp; key.equals(k))))</span><br><span class="line">                        <span class="keyword">return</span> e;</span><br><span class="line">                &#125; <span class="keyword">while</span> ((e = e.next) != <span class="keyword">null</span>);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * Returns &lt;tt&gt;true&lt;/tt&gt; if this map contains a mapping for the</span></span><br><span class="line"><span class="comment">     * specified key.</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span>   key   The key whose presence in this map is to be tested</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span> &lt;tt&gt;true&lt;/tt&gt; if this map contains a mapping for the specified</span></span><br><span class="line"><span class="comment">     * key.</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">containsKey</span><span class="params">(Object key)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> getNode(hash(key), key) != <span class="keyword">null</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * Associates the specified value with the specified key in this map.</span></span><br><span class="line"><span class="comment">     * If the map previously contained a mapping for the key, the old</span></span><br><span class="line"><span class="comment">     * value is replaced.</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> key key with which the specified value is to be associated</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> value value to be associated with the specified key</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span> the previous value associated with &lt;tt&gt;key&lt;/tt&gt;, or</span></span><br><span class="line"><span class="comment">     *         &lt;tt&gt;null&lt;/tt&gt; if there was no mapping for &lt;tt&gt;key&lt;/tt&gt;.</span></span><br><span class="line"><span class="comment">     *         (A &lt;tt&gt;null&lt;/tt&gt; return can also indicate that the map</span></span><br><span class="line"><span class="comment">     *         previously associated &lt;tt&gt;null&lt;/tt&gt; with &lt;tt&gt;key&lt;/tt&gt;.)</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> V <span class="title">put</span><span class="params">(K key, V value)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> putVal(hash(key), key, value, <span class="keyword">false</span>, <span class="keyword">true</span>);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * Implements Map.put and related methods</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> hash hash for key 键经过扰动的哈希值</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> key the key 键</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> value the value to put 值</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> onlyIfAbsent if true, don&#x27;t change existing value 如果要放入的位置为空才放入，不进行替换</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> evict if false, the table is in creation mode.</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span> previous value, or null if none</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">final</span> V <span class="title">putVal</span><span class="params">(<span class="keyword">int</span> hash, K key, V value, <span class="keyword">boolean</span> onlyIfAbsent,</span></span></span><br><span class="line"><span class="function"><span class="params">                   <span class="keyword">boolean</span> evict)</span> </span>&#123;</span><br><span class="line">        <span class="comment">//tab表示当前HashMap的table，p是table的旧的元素，n是散列表的长度，i是路由寻址结果</span></span><br><span class="line">        Node&lt;K,V&gt;[] tab; Node&lt;K,V&gt; p; <span class="keyword">int</span> n, i;</span><br><span class="line">        <span class="comment">//如果table为空，调用resize()方法，初始化table，在第一次用到的时候初始化</span></span><br><span class="line">        <span class="keyword">if</span> ((tab = table) == <span class="keyword">null</span> || (n = tab.length) == <span class="number">0</span>)</span><br><span class="line">            n = (tab = resize()).length;</span><br><span class="line">        <span class="comment">//1.如果要放入的位置刚好为null就直接放入，寻址算法：用与运算替代取模提升性能</span></span><br><span class="line">        <span class="keyword">if</span> ((p = tab[i = (n - <span class="number">1</span>) &amp; hash]) == <span class="keyword">null</span>)</span><br><span class="line">            tab[i] = newNode(hash, key, value, <span class="keyword">null</span>);</span><br><span class="line">        <span class="keyword">else</span> &#123;</span><br><span class="line">        	<span class="comment">//e 存放table中需要修改的元素，k也是需要修改元素的key</span></span><br><span class="line">            Node&lt;K,V&gt; e; K k;</span><br><span class="line">            <span class="comment">//2.当前位置还是数组，放入的位置和你要存的值，键相同，需要进行覆盖操作，将旧值p临时存放到e中</span></span><br><span class="line">            <span class="keyword">if</span> (p.hash == hash &amp;&amp;</span><br><span class="line">                ((k = p.key) == key || (key != <span class="keyword">null</span> &amp;&amp; key.equals(k))))</span><br><span class="line">                e = p;</span><br><span class="line">            <span class="comment">//3.如果当前位置已经树化了</span></span><br><span class="line">            <span class="keyword">else</span> <span class="keyword">if</span> (p <span class="keyword">instanceof</span> TreeNode)</span><br><span class="line">                e = ((TreeNode&lt;K,V&gt;)p).putTreeVal(<span class="keyword">this</span>, tab, hash, key, value);</span><br><span class="line">            <span class="comment">//4.当前位置成为链表</span></span><br><span class="line">            <span class="keyword">else</span> &#123;</span><br><span class="line">                <span class="comment">//循环查找元素</span></span><br><span class="line">                <span class="keyword">for</span> (<span class="keyword">int</span> binCount = <span class="number">0</span>; ; ++binCount) &#123;</span><br><span class="line">                    <span class="comment">//4.1 查到最后一个元素了也没有找到匹配的</span></span><br><span class="line">                    <span class="keyword">if</span> ((e = p.next) == <span class="keyword">null</span>) &#123;</span><br><span class="line">                    	<span class="comment">//最后一个元素再指向新的元素，尾插法，新元素成为末尾节点</span></span><br><span class="line">                        p.next = newNode(hash, key, value, <span class="keyword">null</span>);</span><br><span class="line">                        <span class="comment">//循环值从0开始，所以判断值是否达到树化阈值（条件之一）</span></span><br><span class="line">                        <span class="keyword">if</span> (binCount &gt;= TREEIFY_THRESHOLD - <span class="number">1</span>) <span class="comment">// -1 for 1st</span></span><br><span class="line">                            treeifyBin(tab, hash);</span><br><span class="line">                        <span class="keyword">break</span>;</span><br><span class="line">                    &#125;</span><br><span class="line">                    <span class="comment">//4.2 找到key一致的元素，需要进行覆盖，break结束循环，此时e等于需要替换的元素</span></span><br><span class="line">                    <span class="keyword">if</span> (e.hash == hash &amp;&amp;</span><br><span class="line">                        ((k = e.key) == key || (key != <span class="keyword">null</span> &amp;&amp; key.equals(k))))</span><br><span class="line">                        <span class="keyword">break</span>;</span><br><span class="line">                    <span class="comment">//4.3 查找过程中，没找到对应的也没循环结束。把下一个元素赋给p，继续查找</span></span><br><span class="line">                    p = e;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="comment">//如果找到了需要与插入的元素 key一致的，也就是位置一致的元素</span></span><br><span class="line">            <span class="keyword">if</span> (e != <span class="keyword">null</span>) &#123; <span class="comment">// existing mapping for key</span></span><br><span class="line">            	<span class="comment">//存放旧元素的值</span></span><br><span class="line">                V oldValue = e.value;</span><br><span class="line">                <span class="comment">//先判断参数，不为空是否允许修改</span></span><br><span class="line">                <span class="comment">//如果不为空不允许修改，那么取反就是false，那就看后面的元素值是不是null，空的化就可以修改，妙啊~</span></span><br><span class="line">                <span class="comment">//如果不为空允许修改，那么取反就是true，那就不管空不空都会修改</span></span><br><span class="line">                <span class="keyword">if</span> (!onlyIfAbsent || oldValue == <span class="keyword">null</span>)</span><br><span class="line">                    e.value = value;</span><br><span class="line">                <span class="comment">//为LinkedHashMap预留</span></span><br><span class="line">                afterNodeAccess(e);</span><br><span class="line">                <span class="comment">//返回旧值</span></span><br><span class="line">                <span class="keyword">return</span> oldValue;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//table结构修改次数+1,不包括值替换</span></span><br><span class="line">        ++modCount;</span><br><span class="line">        <span class="comment">//如果元素大小超过阈值时调用resize()方法</span></span><br><span class="line">        <span class="comment">//threshold在第一次put的时候调用过resize()已经计算过</span></span><br><span class="line">        <span class="keyword">if</span> (++size &gt; threshold)</span><br><span class="line">            resize();</span><br><span class="line">        afterNodeInsertion(evict);</span><br><span class="line">        <span class="comment">//没有旧值返回null</span></span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * Initializes or doubles table size.  If null, allocates in</span></span><br><span class="line"><span class="comment">     * accord with initial capacity target held in field threshold.</span></span><br><span class="line"><span class="comment">     * Otherwise, because we are using power-of-two expansion, the</span></span><br><span class="line"><span class="comment">     * elements from each bin must either stay at same index, or move</span></span><br><span class="line"><span class="comment">     * with a power of two offset in the new table.</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span> the table</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">final</span> Node&lt;K,V&gt;[] resize() &#123;</span><br><span class="line">    	<span class="comment">//扩容前的哈希表</span></span><br><span class="line">        Node&lt;K,V&gt;[] oldTab = table;</span><br><span class="line">        <span class="comment">//扩容前的哈希表的长度</span></span><br><span class="line">        <span class="keyword">int</span> oldCap = (oldTab == <span class="keyword">null</span>) ? <span class="number">0</span> : oldTab.length;</span><br><span class="line">        <span class="comment">//树化阈值</span></span><br><span class="line">        <span class="keyword">int</span> oldThr = threshold;</span><br><span class="line">        <span class="comment">//newCap：扩容后的大小</span></span><br><span class="line">        <span class="comment">//newThe：下次触发扩容的阈值</span></span><br><span class="line">        <span class="keyword">int</span> newCap, newThr = <span class="number">0</span>;</span><br><span class="line">        <span class="comment">//1.已经初始化过了，如果扩容前容量&gt;0</span></span><br><span class="line">        <span class="keyword">if</span> (oldCap &gt; <span class="number">0</span>) &#123;</span><br><span class="line">            <span class="comment">//如果扩容前容量大于等于最大容量</span></span><br><span class="line">            <span class="keyword">if</span> (oldCap &gt;= MAXIMUM_CAPACITY) &#123;</span><br><span class="line">           		<span class="comment">//阈值等于最大值，无法扩容返回扩容前的哈希表</span></span><br><span class="line">                threshold = Integer.MAX_VALUE;</span><br><span class="line">                <span class="keyword">return</span> oldTab;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="comment">//左移一位，新容量等于扩容前容量*2</span></span><br><span class="line">            <span class="comment">//新容量小于最大值 并且 大于等于默认值16 </span></span><br><span class="line">            <span class="keyword">else</span> <span class="keyword">if</span> ((newCap = oldCap &lt;&lt; <span class="number">1</span>) &lt; MAXIMUM_CAPACITY &amp;&amp;</span><br><span class="line">                     oldCap &gt;= DEFAULT_INITIAL_CAPACITY)</span><br><span class="line">                <span class="comment">//新阈值也等于原来阈值*2</span></span><br><span class="line">                newThr = oldThr &lt;&lt; <span class="number">1</span>; <span class="comment">// double threshold</span></span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//2.没有初始化过，但是容量传了参数，返回了大于容量的最小2的正式次方幂</span></span><br><span class="line">        <span class="comment">//这种情况出现在初始化哈希表的时候指定了容量，这个时候的阈值等于初始化的容量</span></span><br><span class="line">        <span class="comment">//即：this.threshold = tableSizeFor(initialCapacity);</span></span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> (oldThr &gt; <span class="number">0</span>) <span class="comment">// initial capacity was placed in threshold</span></span><br><span class="line">            newCap = oldThr;</span><br><span class="line">        <span class="comment">//3.没有初始化过，也没有传参，那就是默认长度16，负载因子0.75，阈值为16*0.75</span></span><br><span class="line">        <span class="keyword">else</span> &#123;               <span class="comment">// zero initial threshold signifies using defaults</span></span><br><span class="line">            newCap = DEFAULT_INITIAL_CAPACITY;</span><br><span class="line">            newThr = (<span class="keyword">int</span>)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//即1中的else if条件不满足，旧容量就小于16的情况下，</span></span><br><span class="line">        <span class="comment">//比如最开始容量是4，新容量在else if中 newCap = oldCap &lt;&lt; 1 赋值变成8，</span></span><br><span class="line">        <span class="comment">//但是newThr还是0，那么阈值还是新容量*负载因子=8*0.75= 6</span></span><br><span class="line">        <span class="keyword">if</span> (newThr == <span class="number">0</span>) &#123;</span><br><span class="line">            <span class="keyword">float</span> ft = (<span class="keyword">float</span>)newCap * loadFactor;</span><br><span class="line">            newThr = (newCap &lt; MAXIMUM_CAPACITY &amp;&amp; ft &lt; (<span class="keyword">float</span>)MAXIMUM_CAPACITY ?</span><br><span class="line">                      (<span class="keyword">int</span>)ft : Integer.MAX_VALUE);</span><br><span class="line">        &#125;</span><br><span class="line">        threshold = newThr;</span><br><span class="line">        <span class="comment">//得到新的哈希表</span></span><br><span class="line">        <span class="meta">@SuppressWarnings(&#123;&quot;rawtypes&quot;,&quot;unchecked&quot;&#125;)</span></span><br><span class="line">            Node&lt;K,V&gt;[] newTab = (Node&lt;K,V&gt;[])<span class="keyword">new</span> Node[newCap];</span><br><span class="line">        table = newTab;</span><br><span class="line">        <span class="comment">//如果原先的哈希表不为空，那将数据进行处理</span></span><br><span class="line">        <span class="keyword">if</span> (oldTab != <span class="keyword">null</span>) &#123;</span><br><span class="line">        	<span class="comment">//循环遍历哈希表</span></span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; oldCap; ++j) &#123;</span><br><span class="line">                Node&lt;K,V&gt; e;</span><br><span class="line">                <span class="comment">//如果当前位置不为空，可能是单节点、链表或者是红黑树，赋值给临时变量e</span></span><br><span class="line">                <span class="keyword">if</span> ((e = oldTab[j]) != <span class="keyword">null</span>) &#123;</span><br><span class="line">                	<span class="comment">//将当前位置清空，方便JVM进行回收</span></span><br><span class="line">                    oldTab[j] = <span class="keyword">null</span>;</span><br><span class="line">                    <span class="comment">//1.如果下一个节点为空，那表示这个节点是单节点</span></span><br><span class="line">                    <span class="keyword">if</span> (e.next == <span class="keyword">null</span>)</span><br><span class="line">                    	<span class="comment">//在新的哈希表中寻址，将数据存入</span></span><br><span class="line">                        newTab[e.hash &amp; (newCap - <span class="number">1</span>)] = e;</span><br><span class="line">                    <span class="comment">//2.如果是红黑树的树节点</span></span><br><span class="line">                    <span class="keyword">else</span> <span class="keyword">if</span> (e <span class="keyword">instanceof</span> TreeNode)</span><br><span class="line">                        ((TreeNode&lt;K,V&gt;)e).split(<span class="keyword">this</span>, newTab, j, oldCap);</span><br><span class="line">                    <span class="keyword">else</span> &#123; <span class="comment">// preserve order</span></span><br><span class="line">                    	<span class="comment">//3.如果是链表</span></span><br><span class="line">                    	<span class="comment">//例如：容量为16的哈希表，扩容后为32</span></span><br><span class="line">                    	<span class="comment">//假如说存放在最后下标为15的链表，</span></span><br><span class="line">                    	<span class="comment">//根据寻址算法hash &amp; (16-1) = 1111 = 15，所以存放在下标15的位置，</span></span><br><span class="line">                    	<span class="comment">//但是扩容后算法变成了hash&amp;(32-1) = hash&amp; (0001 1111),</span></span><br><span class="line">                    	<span class="comment">//你并不确定倒数第五位的hash值是0还是1，</span></span><br><span class="line">                    	<span class="comment">//如果是0那就是0 1111 &amp; 1 1111 = 0 1111，放在下标15的位置</span></span><br><span class="line">                    	<span class="comment">//如果是1那就是1 1111 &amp; 1 1111 = 1 1111，放在下标31的位置</span></span><br><span class="line">                        <span class="comment">//低位链表：存放扩容后还在原位置的，比如上面的下标15</span></span><br><span class="line">                        Node&lt;K,V&gt; loHead = <span class="keyword">null</span>, loTail = <span class="keyword">null</span>;</span><br><span class="line">                        <span class="comment">//高位链表：存放扩容后在下标位置+扩容长度的，比如上面的下标31</span></span><br><span class="line">                        Node&lt;K,V&gt; hiHead = <span class="keyword">null</span>, hiTail = <span class="keyword">null</span>; </span><br><span class="line">                        <span class="comment">//存放下一个节点</span></span><br><span class="line">                        Node&lt;K,V&gt; next;</span><br><span class="line">                        <span class="keyword">do</span> &#123;</span><br><span class="line">                        	<span class="comment">//取到下一个节点</span></span><br><span class="line">                            next = e.next;</span><br><span class="line">                            <span class="comment">//如果当前节点的hash &amp; 旧的容量等于0</span></span><br><span class="line">                            <span class="comment">//低位：...0 1111 &amp; 0001 0000 = ...0 0000</span></span><br><span class="line">                            <span class="comment">//高位：...1 1111 &amp; 0001 0000 = ...1 0000</span></span><br><span class="line">                            <span class="keyword">if</span> ((e.hash &amp; oldCap) == <span class="number">0</span>) &#123;</span><br><span class="line">                                <span class="comment">//如果低位链表为空，那头节点就为当前节点</span></span><br><span class="line">                                <span class="keyword">if</span> (loTail == <span class="keyword">null</span>)</span><br><span class="line">                                    loHead = e;</span><br><span class="line">                                <span class="comment">//如果不为空，那就拼接在尾部</span></span><br><span class="line">                                <span class="keyword">else</span></span><br><span class="line">                                    loTail.next = e;</span><br><span class="line">                                loTail = e;</span><br><span class="line">                         		<span class="comment">//这个位置看的云里雾里，画个图豁然开朗</span></span><br><span class="line">                         		<span class="comment">//第一次循环，loHead，loTail都为空，执行loHead = e;e = 									e.next;</span></span><br><span class="line">                         		<span class="comment">//第二次循环，loTail还是为空，执行loTail = e;e = e.next;</span></span><br><span class="line">                         		<span class="comment">//第三次循环，loTail不为空，此时的e已经是第三个节点了，									//	而loTail指向的还是第二个节点，所以loTail.next = e;</span></span><br><span class="line">                         		<span class="comment">//	第二个节点指向第三个节点，再执行loTail = e;将第三个结点								 //	 作为尾结点，也就是始终保持loTail指向的都是尾节点</span></span><br><span class="line">                         		<span class="comment">//  妙啊~</span></span><br><span class="line">                            &#125;</span><br><span class="line">                            <span class="keyword">else</span> &#123;</span><br><span class="line">                                <span class="keyword">if</span> (hiTail == <span class="keyword">null</span>)</span><br><span class="line">                                    hiHead = e;</span><br><span class="line">                                <span class="keyword">else</span></span><br><span class="line">                                    hiTail.next = e;</span><br><span class="line">                                hiTail = e;</span><br><span class="line">                            &#125;</span><br><span class="line">                        &#125; <span class="keyword">while</span> ((e = next) != <span class="keyword">null</span>);</span><br><span class="line">                        <span class="comment">//如果没有下一个节点了，那扩容后低位链表存放在原位置</span></span><br><span class="line">                        <span class="keyword">if</span> (loTail != <span class="keyword">null</span>) &#123;</span><br><span class="line">                            loTail.next = <span class="keyword">null</span>;</span><br><span class="line">                            newTab[j] = loHead;</span><br><span class="line">                        &#125;</span><br><span class="line">                        <span class="comment">//高位链表存放在原来长度+下标位置</span></span><br><span class="line">                        <span class="keyword">if</span> (hiTail != <span class="keyword">null</span>) &#123;</span><br><span class="line">                            hiTail.next = <span class="keyword">null</span>;</span><br><span class="line">                            newTab[j + oldCap] = hiHead;</span><br><span class="line">                        &#125;</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> newTab;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * Replaces all linked nodes in bin at index for given hash unless</span></span><br><span class="line"><span class="comment">     * table is too small, in which case resizes instead.</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">final</span> <span class="keyword">void</span> <span class="title">treeifyBin</span><span class="params">(Node&lt;K,V&gt;[] tab, <span class="keyword">int</span> hash)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> n, index; Node&lt;K,V&gt; e;</span><br><span class="line">        <span class="comment">//如果数字为空或者长度小于最小树化阈值64时，进行扩容</span></span><br><span class="line">        <span class="keyword">if</span> (tab == <span class="keyword">null</span> || (n = tab.length) &lt; MIN_TREEIFY_CAPACITY)</span><br><span class="line">            resize();</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> ((e = tab[index = (n - <span class="number">1</span>) &amp; hash]) != <span class="keyword">null</span>) &#123;</span><br><span class="line">            TreeNode&lt;K,V&gt; hd = <span class="keyword">null</span>, tl = <span class="keyword">null</span>;</span><br><span class="line">            <span class="keyword">do</span> &#123;</span><br><span class="line">                TreeNode&lt;K,V&gt; p = replacementTreeNode(e, <span class="keyword">null</span>);</span><br><span class="line">                <span class="keyword">if</span> (tl == <span class="keyword">null</span>)</span><br><span class="line">                    hd = p;</span><br><span class="line">                <span class="keyword">else</span> &#123;</span><br><span class="line">                    p.prev = tl;</span><br><span class="line">                    tl.next = p;</span><br><span class="line">                &#125;</span><br><span class="line">                tl = p;</span><br><span class="line">            &#125; <span class="keyword">while</span> ((e = e.next) != <span class="keyword">null</span>);</span><br><span class="line">            <span class="keyword">if</span> ((tab[index] = hd) != <span class="keyword">null</span>)</span><br><span class="line">                hd.treeify(tab);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * Copies all of the mappings from the specified map to this map.</span></span><br><span class="line"><span class="comment">     * These mappings will replace any mappings that this map had for</span></span><br><span class="line"><span class="comment">     * any of the keys currently in the specified map.</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> m mappings to be stored in this map</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@throws</span> NullPointerException if the specified map is null</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">putAll</span><span class="params">(Map&lt;? extends K, ? extends V&gt; m)</span> </span>&#123;</span><br><span class="line">        putMapEntries(m, <span class="keyword">true</span>);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * Removes the mapping for the specified key from this map if present.</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span>  key key whose mapping is to be removed from the map</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span> the previous value associated with &lt;tt&gt;key&lt;/tt&gt;, or</span></span><br><span class="line"><span class="comment">     *         &lt;tt&gt;null&lt;/tt&gt; if there was no mapping for &lt;tt&gt;key&lt;/tt&gt;.</span></span><br><span class="line"><span class="comment">     *         (A &lt;tt&gt;null&lt;/tt&gt; return can also indicate that the map</span></span><br><span class="line"><span class="comment">     *         previously associated &lt;tt&gt;null&lt;/tt&gt; with &lt;tt&gt;key&lt;/tt&gt;.)</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> V <span class="title">remove</span><span class="params">(Object key)</span> </span>&#123;</span><br><span class="line">        Node&lt;K,V&gt; e;</span><br><span class="line">        <span class="keyword">return</span> (e = removeNode(hash(key), key, <span class="keyword">null</span>, <span class="keyword">false</span>, <span class="keyword">true</span>)) == <span class="keyword">null</span> ?</span><br><span class="line">            <span class="keyword">null</span> : e.value;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * Implements Map.remove and related methods</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> hash hash for key</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> key the key</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> value the value to match if matchValue, else ignored</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> matchValue if true only remove if value is equal</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> movable if false do not move other nodes while removing</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span> the node, or null if none</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">final</span> Node&lt;K,V&gt; <span class="title">removeNode</span><span class="params">(<span class="keyword">int</span> hash, Object key, Object value,</span></span></span><br><span class="line"><span class="function"><span class="params">                               <span class="keyword">boolean</span> matchValue, <span class="keyword">boolean</span> movable)</span> </span>&#123;</span><br><span class="line">        Node&lt;K,V&gt;[] tab; Node&lt;K,V&gt; p; <span class="keyword">int</span> n, index;</span><br><span class="line">        <span class="keyword">if</span> ((tab = table) != <span class="keyword">null</span> &amp;&amp; (n = tab.length) &gt; <span class="number">0</span> &amp;&amp;</span><br><span class="line">            (p = tab[index = (n - <span class="number">1</span>) &amp; hash]) != <span class="keyword">null</span>) &#123;</span><br><span class="line">            Node&lt;K,V&gt; node = <span class="keyword">null</span>, e; K k; V v;</span><br><span class="line">            <span class="keyword">if</span> (p.hash == hash &amp;&amp;</span><br><span class="line">                ((k = p.key) == key || (key != <span class="keyword">null</span> &amp;&amp; key.equals(k))))</span><br><span class="line">                node = p;</span><br><span class="line">            <span class="keyword">else</span> <span class="keyword">if</span> ((e = p.next) != <span class="keyword">null</span>) &#123;</span><br><span class="line">                <span class="keyword">if</span> (p <span class="keyword">instanceof</span> TreeNode)</span><br><span class="line">                    node = ((TreeNode&lt;K,V&gt;)p).getTreeNode(hash, key);</span><br><span class="line">                <span class="keyword">else</span> &#123;</span><br><span class="line">                    <span class="keyword">do</span> &#123;</span><br><span class="line">                        <span class="keyword">if</span> (e.hash == hash &amp;&amp;</span><br><span class="line">                            ((k = e.key) == key ||</span><br><span class="line">                             (key != <span class="keyword">null</span> &amp;&amp; key.equals(k)))) &#123;</span><br><span class="line">                            node = e;</span><br><span class="line">                            <span class="keyword">break</span>;</span><br><span class="line">                        &#125;</span><br><span class="line">                        p = e;</span><br><span class="line">                    &#125; <span class="keyword">while</span> ((e = e.next) != <span class="keyword">null</span>);</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span> (node != <span class="keyword">null</span> &amp;&amp; (!matchValue || (v = node.value) == value ||</span><br><span class="line">                                 (value != <span class="keyword">null</span> &amp;&amp; value.equals(v)))) &#123;</span><br><span class="line">                <span class="keyword">if</span> (node <span class="keyword">instanceof</span> TreeNode)</span><br><span class="line">                    ((TreeNode&lt;K,V&gt;)node).removeTreeNode(<span class="keyword">this</span>, tab, movable);</span><br><span class="line">                <span class="keyword">else</span> <span class="keyword">if</span> (node == p)</span><br><span class="line">                    tab[index] = node.next;</span><br><span class="line">                <span class="keyword">else</span></span><br><span class="line">                    p.next = node.next;</span><br><span class="line">                ++modCount;</span><br><span class="line">                --size;</span><br><span class="line">                afterNodeRemoval(node);</span><br><span class="line">                <span class="keyword">return</span> node;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * Removes all of the mappings from this map.</span></span><br><span class="line"><span class="comment">     * The map will be empty after this call returns.</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">clear</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        Node&lt;K,V&gt;[] tab;</span><br><span class="line">        modCount++;</span><br><span class="line">        <span class="keyword">if</span> ((tab = table) != <span class="keyword">null</span> &amp;&amp; size &gt; <span class="number">0</span>) &#123;</span><br><span class="line">            size = <span class="number">0</span>;</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; tab.length; ++i)</span><br><span class="line">                tab[i] = <span class="keyword">null</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * Returns &lt;tt&gt;true&lt;/tt&gt; if this map maps one or more keys to the</span></span><br><span class="line"><span class="comment">     * specified value.</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> value value whose presence in this map is to be tested</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span> &lt;tt&gt;true&lt;/tt&gt; if this map maps one or more keys to the</span></span><br><span class="line"><span class="comment">     *         specified value</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">containsValue</span><span class="params">(Object value)</span> </span>&#123;</span><br><span class="line">        Node&lt;K,V&gt;[] tab; V v;</span><br><span class="line">        <span class="keyword">if</span> ((tab = table) != <span class="keyword">null</span> &amp;&amp; size &gt; <span class="number">0</span>) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; tab.length; ++i) &#123;</span><br><span class="line">                <span class="keyword">for</span> (Node&lt;K,V&gt; e = tab[i]; e != <span class="keyword">null</span>; e = e.next) &#123;</span><br><span class="line">                    <span class="keyword">if</span> ((v = e.value) == value ||</span><br><span class="line">                        (value != <span class="keyword">null</span> &amp;&amp; value.equals(v)))</span><br><span class="line">                        <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * Returns a &#123;<span class="doctag">@link</span> Set&#125; view of the keys contained in this map.</span></span><br><span class="line"><span class="comment">     * The set is backed by the map, so changes to the map are</span></span><br><span class="line"><span class="comment">     * reflected in the set, and vice-versa.  If the map is modified</span></span><br><span class="line"><span class="comment">     * while an iteration over the set is in progress (except through</span></span><br><span class="line"><span class="comment">     * the iterator&#x27;s own &lt;tt&gt;remove&lt;/tt&gt; operation), the results of</span></span><br><span class="line"><span class="comment">     * the iteration are undefined.  The set supports element removal,</span></span><br><span class="line"><span class="comment">     * which removes the corresponding mapping from the map, via the</span></span><br><span class="line"><span class="comment">     * &lt;tt&gt;Iterator.remove&lt;/tt&gt;, &lt;tt&gt;Set.remove&lt;/tt&gt;,</span></span><br><span class="line"><span class="comment">     * &lt;tt&gt;removeAll&lt;/tt&gt;, &lt;tt&gt;retainAll&lt;/tt&gt;, and &lt;tt&gt;clear&lt;/tt&gt;</span></span><br><span class="line"><span class="comment">     * operations.  It does not support the &lt;tt&gt;add&lt;/tt&gt; or &lt;tt&gt;addAll&lt;/tt&gt;</span></span><br><span class="line"><span class="comment">     * operations.</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span> a set view of the keys contained in this map</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> Set&lt;K&gt; <span class="title">keySet</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        Set&lt;K&gt; ks;</span><br><span class="line">        <span class="keyword">return</span> (ks = keySet) == <span class="keyword">null</span> ? (keySet = <span class="keyword">new</span> KeySet()) : ks;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">final</span> <span class="class"><span class="keyword">class</span> <span class="title">KeySet</span> <span class="keyword">extends</span> <span class="title">AbstractSet</span>&lt;<span class="title">K</span>&gt; </span>&#123;</span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">final</span> <span class="keyword">int</span> <span class="title">size</span><span class="params">()</span>                 </span>&#123; <span class="keyword">return</span> size; &#125;</span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">final</span> <span class="keyword">void</span> <span class="title">clear</span><span class="params">()</span>               </span>&#123; HashMap.<span class="keyword">this</span>.clear(); &#125;</span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">final</span> Iterator&lt;K&gt; <span class="title">iterator</span><span class="params">()</span>     </span>&#123; <span class="keyword">return</span> <span class="keyword">new</span> KeyIterator(); &#125;</span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">final</span> <span class="keyword">boolean</span> <span class="title">contains</span><span class="params">(Object o)</span> </span>&#123; <span class="keyword">return</span> containsKey(o); &#125;</span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">final</span> <span class="keyword">boolean</span> <span class="title">remove</span><span class="params">(Object key)</span> </span>&#123;</span><br><span class="line">            <span class="keyword">return</span> removeNode(hash(key), key, <span class="keyword">null</span>, <span class="keyword">false</span>, <span class="keyword">true</span>) != <span class="keyword">null</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">final</span> Spliterator&lt;K&gt; <span class="title">spliterator</span><span class="params">()</span> </span>&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">new</span> KeySpliterator&lt;&gt;(HashMap.<span class="keyword">this</span>, <span class="number">0</span>, -<span class="number">1</span>, <span class="number">0</span>, <span class="number">0</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">final</span> <span class="keyword">void</span> <span class="title">forEach</span><span class="params">(Consumer&lt;? <span class="keyword">super</span> K&gt; action)</span> </span>&#123;</span><br><span class="line">            Node&lt;K,V&gt;[] tab;</span><br><span class="line">            <span class="keyword">if</span> (action == <span class="keyword">null</span>)</span><br><span class="line">                <span class="keyword">throw</span> <span class="keyword">new</span> NullPointerException();</span><br><span class="line">            <span class="keyword">if</span> (size &gt; <span class="number">0</span> &amp;&amp; (tab = table) != <span class="keyword">null</span>) &#123;</span><br><span class="line">                <span class="keyword">int</span> mc = modCount;</span><br><span class="line">                <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; tab.length; ++i) &#123;</span><br><span class="line">                    <span class="keyword">for</span> (Node&lt;K,V&gt; e = tab[i]; e != <span class="keyword">null</span>; e = e.next)</span><br><span class="line">                        action.accept(e.key);</span><br><span class="line">                &#125;</span><br><span class="line">                <span class="keyword">if</span> (modCount != mc)</span><br><span class="line">                    <span class="keyword">throw</span> <span class="keyword">new</span> ConcurrentModificationException();</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * Returns a &#123;<span class="doctag">@link</span> Collection&#125; view of the values contained in this map.</span></span><br><span class="line"><span class="comment">     * The collection is backed by the map, so changes to the map are</span></span><br><span class="line"><span class="comment">     * reflected in the collection, and vice-versa.  If the map is</span></span><br><span class="line"><span class="comment">     * modified while an iteration over the collection is in progress</span></span><br><span class="line"><span class="comment">     * (except through the iterator&#x27;s own &lt;tt&gt;remove&lt;/tt&gt; operation),</span></span><br><span class="line"><span class="comment">     * the results of the iteration are undefined.  The collection</span></span><br><span class="line"><span class="comment">     * supports element removal, which removes the corresponding</span></span><br><span class="line"><span class="comment">     * mapping from the map, via the &lt;tt&gt;Iterator.remove&lt;/tt&gt;,</span></span><br><span class="line"><span class="comment">     * &lt;tt&gt;Collection.remove&lt;/tt&gt;, &lt;tt&gt;removeAll&lt;/tt&gt;,</span></span><br><span class="line"><span class="comment">     * &lt;tt&gt;retainAll&lt;/tt&gt; and &lt;tt&gt;clear&lt;/tt&gt; operations.  It does not</span></span><br><span class="line"><span class="comment">     * support the &lt;tt&gt;add&lt;/tt&gt; or &lt;tt&gt;addAll&lt;/tt&gt; operations.</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span> a view of the values contained in this map</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> Collection&lt;V&gt; <span class="title">values</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        Collection&lt;V&gt; vs;</span><br><span class="line">        <span class="keyword">return</span> (vs = values) == <span class="keyword">null</span> ? (values = <span class="keyword">new</span> Values()) : vs;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">final</span> <span class="class"><span class="keyword">class</span> <span class="title">Values</span> <span class="keyword">extends</span> <span class="title">AbstractCollection</span>&lt;<span class="title">V</span>&gt; </span>&#123;</span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">final</span> <span class="keyword">int</span> <span class="title">size</span><span class="params">()</span>                 </span>&#123; <span class="keyword">return</span> size; &#125;</span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">final</span> <span class="keyword">void</span> <span class="title">clear</span><span class="params">()</span>               </span>&#123; HashMap.<span class="keyword">this</span>.clear(); &#125;</span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">final</span> Iterator&lt;V&gt; <span class="title">iterator</span><span class="params">()</span>     </span>&#123; <span class="keyword">return</span> <span class="keyword">new</span> ValueIterator(); &#125;</span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">final</span> <span class="keyword">boolean</span> <span class="title">contains</span><span class="params">(Object o)</span> </span>&#123; <span class="keyword">return</span> containsValue(o); &#125;</span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">final</span> Spliterator&lt;V&gt; <span class="title">spliterator</span><span class="params">()</span> </span>&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">new</span> ValueSpliterator&lt;&gt;(HashMap.<span class="keyword">this</span>, <span class="number">0</span>, -<span class="number">1</span>, <span class="number">0</span>, <span class="number">0</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">final</span> <span class="keyword">void</span> <span class="title">forEach</span><span class="params">(Consumer&lt;? <span class="keyword">super</span> V&gt; action)</span> </span>&#123;</span><br><span class="line">            Node&lt;K,V&gt;[] tab;</span><br><span class="line">            <span class="keyword">if</span> (action == <span class="keyword">null</span>)</span><br><span class="line">                <span class="keyword">throw</span> <span class="keyword">new</span> NullPointerException();</span><br><span class="line">            <span class="keyword">if</span> (size &gt; <span class="number">0</span> &amp;&amp; (tab = table) != <span class="keyword">null</span>) &#123;</span><br><span class="line">                <span class="keyword">int</span> mc = modCount;</span><br><span class="line">                <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; tab.length; ++i) &#123;</span><br><span class="line">                    <span class="keyword">for</span> (Node&lt;K,V&gt; e = tab[i]; e != <span class="keyword">null</span>; e = e.next)</span><br><span class="line">                        action.accept(e.value);</span><br><span class="line">                &#125;</span><br><span class="line">                <span class="keyword">if</span> (modCount != mc)</span><br><span class="line">                    <span class="keyword">throw</span> <span class="keyword">new</span> ConcurrentModificationException();</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * Returns a &#123;<span class="doctag">@link</span> Set&#125; view of the mappings contained in this map.</span></span><br><span class="line"><span class="comment">     * The set is backed by the map, so changes to the map are</span></span><br><span class="line"><span class="comment">     * reflected in the set, and vice-versa.  If the map is modified</span></span><br><span class="line"><span class="comment">     * while an iteration over the set is in progress (except through</span></span><br><span class="line"><span class="comment">     * the iterator&#x27;s own &lt;tt&gt;remove&lt;/tt&gt; operation, or through the</span></span><br><span class="line"><span class="comment">     * &lt;tt&gt;setValue&lt;/tt&gt; operation on a map entry returned by the</span></span><br><span class="line"><span class="comment">     * iterator) the results of the iteration are undefined.  The set</span></span><br><span class="line"><span class="comment">     * supports element removal, which removes the corresponding</span></span><br><span class="line"><span class="comment">     * mapping from the map, via the &lt;tt&gt;Iterator.remove&lt;/tt&gt;,</span></span><br><span class="line"><span class="comment">     * &lt;tt&gt;Set.remove&lt;/tt&gt;, &lt;tt&gt;removeAll&lt;/tt&gt;, &lt;tt&gt;retainAll&lt;/tt&gt; and</span></span><br><span class="line"><span class="comment">     * &lt;tt&gt;clear&lt;/tt&gt; operations.  It does not support the</span></span><br><span class="line"><span class="comment">     * &lt;tt&gt;add&lt;/tt&gt; or &lt;tt&gt;addAll&lt;/tt&gt; operations.</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span> a set view of the mappings contained in this map</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">public</span> Set&lt;Map.Entry&lt;K,V&gt;&gt; entrySet() &#123;</span><br><span class="line">        Set&lt;Map.Entry&lt;K,V&gt;&gt; es;</span><br><span class="line">        <span class="keyword">return</span> (es = entrySet) == <span class="keyword">null</span> ? (entrySet = <span class="keyword">new</span> EntrySet()) : es;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">final</span> <span class="class"><span class="keyword">class</span> <span class="title">EntrySet</span> <span class="keyword">extends</span> <span class="title">AbstractSet</span>&lt;<span class="title">Map</span>.<span class="title">Entry</span>&lt;<span class="title">K</span>,<span class="title">V</span>&gt;&gt; </span>&#123;</span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">final</span> <span class="keyword">int</span> <span class="title">size</span><span class="params">()</span>                 </span>&#123; <span class="keyword">return</span> size; &#125;</span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">final</span> <span class="keyword">void</span> <span class="title">clear</span><span class="params">()</span>               </span>&#123; HashMap.<span class="keyword">this</span>.clear(); &#125;</span><br><span class="line">        <span class="keyword">public</span> <span class="keyword">final</span> Iterator&lt;Map.Entry&lt;K,V&gt;&gt; iterator() &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">new</span> EntryIterator();</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">final</span> <span class="keyword">boolean</span> <span class="title">contains</span><span class="params">(Object o)</span> </span>&#123;</span><br><span class="line">            <span class="keyword">if</span> (!(o <span class="keyword">instanceof</span> Map.Entry))</span><br><span class="line">                <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">            Map.Entry&lt;?,?&gt; e = (Map.Entry&lt;?,?&gt;) o;</span><br><span class="line">            Object key = e.getKey();</span><br><span class="line">            Node&lt;K,V&gt; candidate = getNode(hash(key), key);</span><br><span class="line">            <span class="keyword">return</span> candidate != <span class="keyword">null</span> &amp;&amp; candidate.equals(e);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">final</span> <span class="keyword">boolean</span> <span class="title">remove</span><span class="params">(Object o)</span> </span>&#123;</span><br><span class="line">            <span class="keyword">if</span> (o <span class="keyword">instanceof</span> Map.Entry) &#123;</span><br><span class="line">                Map.Entry&lt;?,?&gt; e = (Map.Entry&lt;?,?&gt;) o;</span><br><span class="line">                Object key = e.getKey();</span><br><span class="line">                Object value = e.getValue();</span><br><span class="line">                <span class="keyword">return</span> removeNode(hash(key), key, value, <span class="keyword">true</span>, <span class="keyword">true</span>) != <span class="keyword">null</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">public</span> <span class="keyword">final</span> Spliterator&lt;Map.Entry&lt;K,V&gt;&gt; spliterator() &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">new</span> EntrySpliterator&lt;&gt;(HashMap.<span class="keyword">this</span>, <span class="number">0</span>, -<span class="number">1</span>, <span class="number">0</span>, <span class="number">0</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">final</span> <span class="keyword">void</span> <span class="title">forEach</span><span class="params">(Consumer&lt;? <span class="keyword">super</span> Map.Entry&lt;K,V&gt;&gt; action)</span> </span>&#123;</span><br><span class="line">            Node&lt;K,V&gt;[] tab;</span><br><span class="line">            <span class="keyword">if</span> (action == <span class="keyword">null</span>)</span><br><span class="line">                <span class="keyword">throw</span> <span class="keyword">new</span> NullPointerException();</span><br><span class="line">            <span class="keyword">if</span> (size &gt; <span class="number">0</span> &amp;&amp; (tab = table) != <span class="keyword">null</span>) &#123;</span><br><span class="line">                <span class="keyword">int</span> mc = modCount;</span><br><span class="line">                <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; tab.length; ++i) &#123;</span><br><span class="line">                    <span class="keyword">for</span> (Node&lt;K,V&gt; e = tab[i]; e != <span class="keyword">null</span>; e = e.next)</span><br><span class="line">                        action.accept(e);</span><br><span class="line">                &#125;</span><br><span class="line">                <span class="keyword">if</span> (modCount != mc)</span><br><span class="line">                    <span class="keyword">throw</span> <span class="keyword">new</span> ConcurrentModificationException();</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// Overrides of JDK8 Map extension methods</span></span><br><span class="line"></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> V <span class="title">getOrDefault</span><span class="params">(Object key, V defaultValue)</span> </span>&#123;</span><br><span class="line">        Node&lt;K,V&gt; e;</span><br><span class="line">        <span class="keyword">return</span> (e = getNode(hash(key), key)) == <span class="keyword">null</span> ? defaultValue : e.value;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> V <span class="title">putIfAbsent</span><span class="params">(K key, V value)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> putVal(hash(key), key, value, <span class="keyword">true</span>, <span class="keyword">true</span>);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">remove</span><span class="params">(Object key, Object value)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> removeNode(hash(key), key, value, <span class="keyword">true</span>, <span class="keyword">true</span>) != <span class="keyword">null</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">replace</span><span class="params">(K key, V oldValue, V newValue)</span> </span>&#123;</span><br><span class="line">        Node&lt;K,V&gt; e; V v;</span><br><span class="line">        <span class="keyword">if</span> ((e = getNode(hash(key), key)) != <span class="keyword">null</span> &amp;&amp;</span><br><span class="line">            ((v = e.value) == oldValue || (v != <span class="keyword">null</span> &amp;&amp; v.equals(oldValue)))) &#123;</span><br><span class="line">            e.value = newValue;</span><br><span class="line">            afterNodeAccess(e);</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> V <span class="title">replace</span><span class="params">(K key, V value)</span> </span>&#123;</span><br><span class="line">        Node&lt;K,V&gt; e;</span><br><span class="line">        <span class="keyword">if</span> ((e = getNode(hash(key), key)) != <span class="keyword">null</span>) &#123;</span><br><span class="line">            V oldValue = e.value;</span><br><span class="line">            e.value = value;</span><br><span class="line">            afterNodeAccess(e);</span><br><span class="line">            <span class="keyword">return</span> oldValue;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> V <span class="title">computeIfAbsent</span><span class="params">(K key,</span></span></span><br><span class="line"><span class="function"><span class="params">                             Function&lt;? <span class="keyword">super</span> K, ? extends V&gt; mappingFunction)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (mappingFunction == <span class="keyword">null</span>)</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> NullPointerException();</span><br><span class="line">        <span class="keyword">int</span> hash = hash(key);</span><br><span class="line">        Node&lt;K,V&gt;[] tab; Node&lt;K,V&gt; first; <span class="keyword">int</span> n, i;</span><br><span class="line">        <span class="keyword">int</span> binCount = <span class="number">0</span>;</span><br><span class="line">        TreeNode&lt;K,V&gt; t = <span class="keyword">null</span>;</span><br><span class="line">        Node&lt;K,V&gt; old = <span class="keyword">null</span>;</span><br><span class="line">        <span class="keyword">if</span> (size &gt; threshold || (tab = table) == <span class="keyword">null</span> ||</span><br><span class="line">            (n = tab.length) == <span class="number">0</span>)</span><br><span class="line">            n = (tab = resize()).length;</span><br><span class="line">        <span class="keyword">if</span> ((first = tab[i = (n - <span class="number">1</span>) &amp; hash]) != <span class="keyword">null</span>) &#123;</span><br><span class="line">            <span class="keyword">if</span> (first <span class="keyword">instanceof</span> TreeNode)</span><br><span class="line">                old = (t = (TreeNode&lt;K,V&gt;)first).getTreeNode(hash, key);</span><br><span class="line">            <span class="keyword">else</span> &#123;</span><br><span class="line">                Node&lt;K,V&gt; e = first; K k;</span><br><span class="line">                <span class="keyword">do</span> &#123;</span><br><span class="line">                    <span class="keyword">if</span> (e.hash == hash &amp;&amp;</span><br><span class="line">                        ((k = e.key) == key || (key != <span class="keyword">null</span> &amp;&amp; key.equals(k)))) &#123;</span><br><span class="line">                        old = e;</span><br><span class="line">                        <span class="keyword">break</span>;</span><br><span class="line">                    &#125;</span><br><span class="line">                    ++binCount;</span><br><span class="line">                &#125; <span class="keyword">while</span> ((e = e.next) != <span class="keyword">null</span>);</span><br><span class="line">            &#125;</span><br><span class="line">            V oldValue;</span><br><span class="line">            <span class="keyword">if</span> (old != <span class="keyword">null</span> &amp;&amp; (oldValue = old.value) != <span class="keyword">null</span>) &#123;</span><br><span class="line">                afterNodeAccess(old);</span><br><span class="line">                <span class="keyword">return</span> oldValue;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        V v = mappingFunction.apply(key);</span><br><span class="line">        <span class="keyword">if</span> (v == <span class="keyword">null</span>) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">        &#125; <span class="keyword">else</span> <span class="keyword">if</span> (old != <span class="keyword">null</span>) &#123;</span><br><span class="line">            old.value = v;</span><br><span class="line">            afterNodeAccess(old);</span><br><span class="line">            <span class="keyword">return</span> v;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> (t != <span class="keyword">null</span>)</span><br><span class="line">            t.putTreeVal(<span class="keyword">this</span>, tab, hash, key, v);</span><br><span class="line">        <span class="keyword">else</span> &#123;</span><br><span class="line">            tab[i] = newNode(hash, key, v, first);</span><br><span class="line">            <span class="keyword">if</span> (binCount &gt;= TREEIFY_THRESHOLD - <span class="number">1</span>)</span><br><span class="line">                treeifyBin(tab, hash);</span><br><span class="line">        &#125;</span><br><span class="line">        ++modCount;</span><br><span class="line">        ++size;</span><br><span class="line">        afterNodeInsertion(<span class="keyword">true</span>);</span><br><span class="line">        <span class="keyword">return</span> v;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> V <span class="title">computeIfPresent</span><span class="params">(K key,</span></span></span><br><span class="line"><span class="function"><span class="params">                              BiFunction&lt;? <span class="keyword">super</span> K, ? <span class="keyword">super</span> V, ? extends V&gt; remappingFunction)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (remappingFunction == <span class="keyword">null</span>)</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> NullPointerException();</span><br><span class="line">        Node&lt;K,V&gt; e; V oldValue;</span><br><span class="line">        <span class="keyword">int</span> hash = hash(key);</span><br><span class="line">        <span class="keyword">if</span> ((e = getNode(hash, key)) != <span class="keyword">null</span> &amp;&amp;</span><br><span class="line">            (oldValue = e.value) != <span class="keyword">null</span>) &#123;</span><br><span class="line">            V v = remappingFunction.apply(key, oldValue);</span><br><span class="line">            <span class="keyword">if</span> (v != <span class="keyword">null</span>) &#123;</span><br><span class="line">                e.value = v;</span><br><span class="line">                afterNodeAccess(e);</span><br><span class="line">                <span class="keyword">return</span> v;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">else</span></span><br><span class="line">                removeNode(hash, key, <span class="keyword">null</span>, <span class="keyword">false</span>, <span class="keyword">true</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> V <span class="title">compute</span><span class="params">(K key,</span></span></span><br><span class="line"><span class="function"><span class="params">                     BiFunction&lt;? <span class="keyword">super</span> K, ? <span class="keyword">super</span> V, ? extends V&gt; remappingFunction)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (remappingFunction == <span class="keyword">null</span>)</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> NullPointerException();</span><br><span class="line">        <span class="keyword">int</span> hash = hash(key);</span><br><span class="line">        Node&lt;K,V&gt;[] tab; Node&lt;K,V&gt; first; <span class="keyword">int</span> n, i;</span><br><span class="line">        <span class="keyword">int</span> binCount = <span class="number">0</span>;</span><br><span class="line">        TreeNode&lt;K,V&gt; t = <span class="keyword">null</span>;</span><br><span class="line">        Node&lt;K,V&gt; old = <span class="keyword">null</span>;</span><br><span class="line">        <span class="keyword">if</span> (size &gt; threshold || (tab = table) == <span class="keyword">null</span> ||</span><br><span class="line">            (n = tab.length) == <span class="number">0</span>)</span><br><span class="line">            n = (tab = resize()).length;</span><br><span class="line">        <span class="keyword">if</span> ((first = tab[i = (n - <span class="number">1</span>) &amp; hash]) != <span class="keyword">null</span>) &#123;</span><br><span class="line">            <span class="keyword">if</span> (first <span class="keyword">instanceof</span> TreeNode)</span><br><span class="line">                old = (t = (TreeNode&lt;K,V&gt;)first).getTreeNode(hash, key);</span><br><span class="line">            <span class="keyword">else</span> &#123;</span><br><span class="line">                Node&lt;K,V&gt; e = first; K k;</span><br><span class="line">                <span class="keyword">do</span> &#123;</span><br><span class="line">                    <span class="keyword">if</span> (e.hash == hash &amp;&amp;</span><br><span class="line">                        ((k = e.key) == key || (key != <span class="keyword">null</span> &amp;&amp; key.equals(k)))) &#123;</span><br><span class="line">                        old = e;</span><br><span class="line">                        <span class="keyword">break</span>;</span><br><span class="line">                    &#125;</span><br><span class="line">                    ++binCount;</span><br><span class="line">                &#125; <span class="keyword">while</span> ((e = e.next) != <span class="keyword">null</span>);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        V oldValue = (old == <span class="keyword">null</span>) ? <span class="keyword">null</span> : old.value;</span><br><span class="line">        V v = remappingFunction.apply(key, oldValue);</span><br><span class="line">        <span class="keyword">if</span> (old != <span class="keyword">null</span>) &#123;</span><br><span class="line">            <span class="keyword">if</span> (v != <span class="keyword">null</span>) &#123;</span><br><span class="line">                old.value = v;</span><br><span class="line">                afterNodeAccess(old);</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">else</span></span><br><span class="line">                removeNode(hash, key, <span class="keyword">null</span>, <span class="keyword">false</span>, <span class="keyword">true</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> (v != <span class="keyword">null</span>) &#123;</span><br><span class="line">            <span class="keyword">if</span> (t != <span class="keyword">null</span>)</span><br><span class="line">                t.putTreeVal(<span class="keyword">this</span>, tab, hash, key, v);</span><br><span class="line">            <span class="keyword">else</span> &#123;</span><br><span class="line">                tab[i] = newNode(hash, key, v, first);</span><br><span class="line">                <span class="keyword">if</span> (binCount &gt;= TREEIFY_THRESHOLD - <span class="number">1</span>)</span><br><span class="line">                    treeifyBin(tab, hash);</span><br><span class="line">            &#125;</span><br><span class="line">            ++modCount;</span><br><span class="line">            ++size;</span><br><span class="line">            afterNodeInsertion(<span class="keyword">true</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> v;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> V <span class="title">merge</span><span class="params">(K key, V value,</span></span></span><br><span class="line"><span class="function"><span class="params">                   BiFunction&lt;? <span class="keyword">super</span> V, ? <span class="keyword">super</span> V, ? extends V&gt; remappingFunction)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (value == <span class="keyword">null</span>)</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> NullPointerException();</span><br><span class="line">        <span class="keyword">if</span> (remappingFunction == <span class="keyword">null</span>)</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> NullPointerException();</span><br><span class="line">        <span class="keyword">int</span> hash = hash(key);</span><br><span class="line">        Node&lt;K,V&gt;[] tab; Node&lt;K,V&gt; first; <span class="keyword">int</span> n, i;</span><br><span class="line">        <span class="keyword">int</span> binCount = <span class="number">0</span>;</span><br><span class="line">        TreeNode&lt;K,V&gt; t = <span class="keyword">null</span>;</span><br><span class="line">        Node&lt;K,V&gt; old = <span class="keyword">null</span>;</span><br><span class="line">        <span class="keyword">if</span> (size &gt; threshold || (tab = table) == <span class="keyword">null</span> ||</span><br><span class="line">            (n = tab.length) == <span class="number">0</span>)</span><br><span class="line">            n = (tab = resize()).length;</span><br><span class="line">        <span class="keyword">if</span> ((first = tab[i = (n - <span class="number">1</span>) &amp; hash]) != <span class="keyword">null</span>) &#123;</span><br><span class="line">            <span class="keyword">if</span> (first <span class="keyword">instanceof</span> TreeNode)</span><br><span class="line">                old = (t = (TreeNode&lt;K,V&gt;)first).getTreeNode(hash, key);</span><br><span class="line">            <span class="keyword">else</span> &#123;</span><br><span class="line">                Node&lt;K,V&gt; e = first; K k;</span><br><span class="line">                <span class="keyword">do</span> &#123;</span><br><span class="line">                    <span class="keyword">if</span> (e.hash == hash &amp;&amp;</span><br><span class="line">                        ((k = e.key) == key || (key != <span class="keyword">null</span> &amp;&amp; key.equals(k)))) &#123;</span><br><span class="line">                        old = e;</span><br><span class="line">                        <span class="keyword">break</span>;</span><br><span class="line">                    &#125;</span><br><span class="line">                    ++binCount;</span><br><span class="line">                &#125; <span class="keyword">while</span> ((e = e.next) != <span class="keyword">null</span>);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (old != <span class="keyword">null</span>) &#123;</span><br><span class="line">            V v;</span><br><span class="line">            <span class="keyword">if</span> (old.value != <span class="keyword">null</span>)</span><br><span class="line">                v = remappingFunction.apply(old.value, value);</span><br><span class="line">            <span class="keyword">else</span></span><br><span class="line">                v = value;</span><br><span class="line">            <span class="keyword">if</span> (v != <span class="keyword">null</span>) &#123;</span><br><span class="line">                old.value = v;</span><br><span class="line">                afterNodeAccess(old);</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">else</span></span><br><span class="line">                removeNode(hash, key, <span class="keyword">null</span>, <span class="keyword">false</span>, <span class="keyword">true</span>);</span><br><span class="line">            <span class="keyword">return</span> v;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (value != <span class="keyword">null</span>) &#123;</span><br><span class="line">            <span class="keyword">if</span> (t != <span class="keyword">null</span>)</span><br><span class="line">                t.putTreeVal(<span class="keyword">this</span>, tab, hash, key, value);</span><br><span class="line">            <span class="keyword">else</span> &#123;</span><br><span class="line">                tab[i] = newNode(hash, key, value, first);</span><br><span class="line">                <span class="keyword">if</span> (binCount &gt;= TREEIFY_THRESHOLD - <span class="number">1</span>)</span><br><span class="line">                    treeifyBin(tab, hash);</span><br><span class="line">            &#125;</span><br><span class="line">            ++modCount;</span><br><span class="line">            ++size;</span><br><span class="line">            afterNodeInsertion(<span class="keyword">true</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> value;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">forEach</span><span class="params">(BiConsumer&lt;? <span class="keyword">super</span> K, ? <span class="keyword">super</span> V&gt; action)</span> </span>&#123;</span><br><span class="line">        Node&lt;K,V&gt;[] tab;</span><br><span class="line">        <span class="keyword">if</span> (action == <span class="keyword">null</span>)</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> NullPointerException();</span><br><span class="line">        <span class="keyword">if</span> (size &gt; <span class="number">0</span> &amp;&amp; (tab = table) != <span class="keyword">null</span>) &#123;</span><br><span class="line">            <span class="keyword">int</span> mc = modCount;</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; tab.length; ++i) &#123;</span><br><span class="line">                <span class="keyword">for</span> (Node&lt;K,V&gt; e = tab[i]; e != <span class="keyword">null</span>; e = e.next)</span><br><span class="line">                    action.accept(e.key, e.value);</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span> (modCount != mc)</span><br><span class="line">                <span class="keyword">throw</span> <span class="keyword">new</span> ConcurrentModificationException();</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">replaceAll</span><span class="params">(BiFunction&lt;? <span class="keyword">super</span> K, ? <span class="keyword">super</span> V, ? extends V&gt; function)</span> </span>&#123;</span><br><span class="line">        Node&lt;K,V&gt;[] tab;</span><br><span class="line">        <span class="keyword">if</span> (function == <span class="keyword">null</span>)</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> NullPointerException();</span><br><span class="line">        <span class="keyword">if</span> (size &gt; <span class="number">0</span> &amp;&amp; (tab = table) != <span class="keyword">null</span>) &#123;</span><br><span class="line">            <span class="keyword">int</span> mc = modCount;</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; tab.length; ++i) &#123;</span><br><span class="line">                <span class="keyword">for</span> (Node&lt;K,V&gt; e = tab[i]; e != <span class="keyword">null</span>; e = e.next) &#123;</span><br><span class="line">                    e.value = function.apply(e.key, e.value);</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span> (modCount != mc)</span><br><span class="line">                <span class="keyword">throw</span> <span class="keyword">new</span> ConcurrentModificationException();</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/* ------------------------------------------------------------ */</span></span><br><span class="line">    <span class="comment">// Cloning and serialization</span></span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * Returns a shallow copy of this &lt;tt&gt;HashMap&lt;/tt&gt; instance: the keys and</span></span><br><span class="line"><span class="comment">     * values themselves are not cloned.</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span> a shallow copy of this map</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="meta">@SuppressWarnings(&quot;unchecked&quot;)</span></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> Object <span class="title">clone</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        HashMap&lt;K,V&gt; result;</span><br><span class="line">        <span class="keyword">try</span> &#123;</span><br><span class="line">            result = (HashMap&lt;K,V&gt;)<span class="keyword">super</span>.clone();</span><br><span class="line">        &#125; <span class="keyword">catch</span> (CloneNotSupportedException e) &#123;</span><br><span class="line">            <span class="comment">// this shouldn&#x27;t happen, since we are Cloneable</span></span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> InternalError(e);</span><br><span class="line">        &#125;</span><br><span class="line">        result.reinitialize();</span><br><span class="line">        result.putMapEntries(<span class="keyword">this</span>, <span class="keyword">false</span>);</span><br><span class="line">        <span class="keyword">return</span> result;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// These methods are also used when serializing HashSets</span></span><br><span class="line">    <span class="function"><span class="keyword">final</span> <span class="keyword">float</span> <span class="title">loadFactor</span><span class="params">()</span> </span>&#123; <span class="keyword">return</span> loadFactor; &#125;</span><br><span class="line">    <span class="function"><span class="keyword">final</span> <span class="keyword">int</span> <span class="title">capacity</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> (table != <span class="keyword">null</span>) ? table.length :</span><br><span class="line">            (threshold &gt; <span class="number">0</span>) ? threshold :</span><br><span class="line">            DEFAULT_INITIAL_CAPACITY;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * Save the state of the &lt;tt&gt;HashMap&lt;/tt&gt; instance to a stream (i.e.,</span></span><br><span class="line"><span class="comment">     * serialize it).</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@serialData</span> The &lt;i&gt;capacity&lt;/i&gt; of the HashMap (the length of the</span></span><br><span class="line"><span class="comment">     *             bucket array) is emitted (int), followed by the</span></span><br><span class="line"><span class="comment">     *             &lt;i&gt;size&lt;/i&gt; (an int, the number of key-value</span></span><br><span class="line"><span class="comment">     *             mappings), followed by the key (Object) and value (Object)</span></span><br><span class="line"><span class="comment">     *             for each key-value mapping.  The key-value mappings are</span></span><br><span class="line"><span class="comment">     *             emitted in no particular order.</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">writeObject</span><span class="params">(java.io.ObjectOutputStream s)</span></span></span><br><span class="line"><span class="function">        <span class="keyword">throws</span> IOException </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> buckets = capacity();</span><br><span class="line">        <span class="comment">// Write out the threshold, loadfactor, and any hidden stuff</span></span><br><span class="line">        s.defaultWriteObject();</span><br><span class="line">        s.writeInt(buckets);</span><br><span class="line">        s.writeInt(size);</span><br><span class="line">        internalWriteEntries(s);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * Reconstitute the &#123;<span class="doctag">@code</span> HashMap&#125; instance from a stream (i.e.,</span></span><br><span class="line"><span class="comment">     * deserialize it).</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">readObject</span><span class="params">(java.io.ObjectInputStream s)</span></span></span><br><span class="line"><span class="function">        <span class="keyword">throws</span> IOException, ClassNotFoundException </span>&#123;</span><br><span class="line">        <span class="comment">// Read in the threshold (ignored), loadfactor, and any hidden stuff</span></span><br><span class="line">        s.defaultReadObject();</span><br><span class="line">        reinitialize();</span><br><span class="line">        <span class="keyword">if</span> (loadFactor &lt;= <span class="number">0</span> || Float.isNaN(loadFactor))</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> InvalidObjectException(<span class="string">&quot;Illegal load factor: &quot;</span> +</span><br><span class="line">                                             loadFactor);</span><br><span class="line">        s.readInt();                <span class="comment">// Read and ignore number of buckets</span></span><br><span class="line">        <span class="keyword">int</span> mappings = s.readInt(); <span class="comment">// Read number of mappings (size)</span></span><br><span class="line">        <span class="keyword">if</span> (mappings &lt; <span class="number">0</span>)</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> InvalidObjectException(<span class="string">&quot;Illegal mappings count: &quot;</span> +</span><br><span class="line">                                             mappings);</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> (mappings &gt; <span class="number">0</span>) &#123; <span class="comment">// (if zero, use defaults)</span></span><br><span class="line">            <span class="comment">// Size the table using given load factor only if within</span></span><br><span class="line">            <span class="comment">// range of 0.25...4.0</span></span><br><span class="line">            <span class="keyword">float</span> lf = Math.min(Math.max(<span class="number">0.25f</span>, loadFactor), <span class="number">4.0f</span>);</span><br><span class="line">            <span class="keyword">float</span> fc = (<span class="keyword">float</span>)mappings / lf + <span class="number">1.0f</span>;</span><br><span class="line">            <span class="keyword">int</span> cap = ((fc &lt; DEFAULT_INITIAL_CAPACITY) ?</span><br><span class="line">                       DEFAULT_INITIAL_CAPACITY :</span><br><span class="line">                       (fc &gt;= MAXIMUM_CAPACITY) ?</span><br><span class="line">                       MAXIMUM_CAPACITY :</span><br><span class="line">                       tableSizeFor((<span class="keyword">int</span>)fc));</span><br><span class="line">            <span class="keyword">float</span> ft = (<span class="keyword">float</span>)cap * lf;</span><br><span class="line">            threshold = ((cap &lt; MAXIMUM_CAPACITY &amp;&amp; ft &lt; MAXIMUM_CAPACITY) ?</span><br><span class="line">                         (<span class="keyword">int</span>)ft : Integer.MAX_VALUE);</span><br><span class="line">            <span class="meta">@SuppressWarnings(&#123;&quot;rawtypes&quot;,&quot;unchecked&quot;&#125;)</span></span><br><span class="line">                Node&lt;K,V&gt;[] tab = (Node&lt;K,V&gt;[])<span class="keyword">new</span> Node[cap];</span><br><span class="line">            table = tab;</span><br><span class="line"></span><br><span class="line">            <span class="comment">// Read the keys and values, and put the mappings in the HashMap</span></span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; mappings; i++) &#123;</span><br><span class="line">                <span class="meta">@SuppressWarnings(&quot;unchecked&quot;)</span></span><br><span class="line">                    K key = (K) s.readObject();</span><br><span class="line">                <span class="meta">@SuppressWarnings(&quot;unchecked&quot;)</span></span><br><span class="line">                    V value = (V) s.readObject();</span><br><span class="line">                putVal(hash(key), key, value, <span class="keyword">false</span>, <span class="keyword">false</span>);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/* ------------------------------------------------------------ */</span></span><br><span class="line">    <span class="comment">// iterators</span></span><br><span class="line"></span><br><span class="line">    <span class="keyword">abstract</span> <span class="class"><span class="keyword">class</span> <span class="title">HashIterator</span> </span>&#123;</span><br><span class="line">        Node&lt;K,V&gt; next;        <span class="comment">// next entry to return</span></span><br><span class="line">        Node&lt;K,V&gt; current;     <span class="comment">// current entry</span></span><br><span class="line">        <span class="keyword">int</span> expectedModCount;  <span class="comment">// for fast-fail</span></span><br><span class="line">        <span class="keyword">int</span> index;             <span class="comment">// current slot</span></span><br><span class="line"></span><br><span class="line">        HashIterator() &#123;</span><br><span class="line">            expectedModCount = modCount;</span><br><span class="line">            Node&lt;K,V&gt;[] t = table;</span><br><span class="line">            current = next = <span class="keyword">null</span>;</span><br><span class="line">            index = <span class="number">0</span>;</span><br><span class="line">            <span class="keyword">if</span> (t != <span class="keyword">null</span> &amp;&amp; size &gt; <span class="number">0</span>) &#123; <span class="comment">// advance to first entry</span></span><br><span class="line">                <span class="keyword">do</span> &#123;&#125; <span class="keyword">while</span> (index &lt; t.length &amp;&amp; (next = t[index++]) == <span class="keyword">null</span>);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">final</span> <span class="keyword">boolean</span> <span class="title">hasNext</span><span class="params">()</span> </span>&#123;</span><br><span class="line">            <span class="keyword">return</span> next != <span class="keyword">null</span>;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">final</span> Node&lt;K,V&gt; <span class="title">nextNode</span><span class="params">()</span> </span>&#123;</span><br><span class="line">            Node&lt;K,V&gt;[] t;</span><br><span class="line">            Node&lt;K,V&gt; e = next;</span><br><span class="line">            <span class="keyword">if</span> (modCount != expectedModCount)</span><br><span class="line">                <span class="keyword">throw</span> <span class="keyword">new</span> ConcurrentModificationException();</span><br><span class="line">            <span class="keyword">if</span> (e == <span class="keyword">null</span>)</span><br><span class="line">                <span class="keyword">throw</span> <span class="keyword">new</span> NoSuchElementException();</span><br><span class="line">            <span class="keyword">if</span> ((next = (current = e).next) == <span class="keyword">null</span> &amp;&amp; (t = table) != <span class="keyword">null</span>) &#123;</span><br><span class="line">                <span class="keyword">do</span> &#123;&#125; <span class="keyword">while</span> (index &lt; t.length &amp;&amp; (next = t[index++]) == <span class="keyword">null</span>);</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">return</span> e;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">final</span> <span class="keyword">void</span> <span class="title">remove</span><span class="params">()</span> </span>&#123;</span><br><span class="line">            Node&lt;K,V&gt; p = current;</span><br><span class="line">            <span class="keyword">if</span> (p == <span class="keyword">null</span>)</span><br><span class="line">                <span class="keyword">throw</span> <span class="keyword">new</span> IllegalStateException();</span><br><span class="line">            <span class="keyword">if</span> (modCount != expectedModCount)</span><br><span class="line">                <span class="keyword">throw</span> <span class="keyword">new</span> ConcurrentModificationException();</span><br><span class="line">            current = <span class="keyword">null</span>;</span><br><span class="line">            K key = p.key;</span><br><span class="line">            removeNode(hash(key), key, <span class="keyword">null</span>, <span class="keyword">false</span>, <span class="keyword">false</span>);</span><br><span class="line">            expectedModCount = modCount;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">final</span> <span class="class"><span class="keyword">class</span> <span class="title">KeyIterator</span> <span class="keyword">extends</span> <span class="title">HashIterator</span></span></span><br><span class="line"><span class="class">        <span class="keyword">implements</span> <span class="title">Iterator</span>&lt;<span class="title">K</span>&gt; </span>&#123;</span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">final</span> K <span class="title">next</span><span class="params">()</span> </span>&#123; <span class="keyword">return</span> nextNode().key; &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">final</span> <span class="class"><span class="keyword">class</span> <span class="title">ValueIterator</span> <span class="keyword">extends</span> <span class="title">HashIterator</span></span></span><br><span class="line"><span class="class">        <span class="keyword">implements</span> <span class="title">Iterator</span>&lt;<span class="title">V</span>&gt; </span>&#123;</span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">final</span> V <span class="title">next</span><span class="params">()</span> </span>&#123; <span class="keyword">return</span> nextNode().value; &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">final</span> <span class="class"><span class="keyword">class</span> <span class="title">EntryIterator</span> <span class="keyword">extends</span> <span class="title">HashIterator</span></span></span><br><span class="line"><span class="class">        <span class="keyword">implements</span> <span class="title">Iterator</span>&lt;<span class="title">Map</span>.<span class="title">Entry</span>&lt;<span class="title">K</span>,<span class="title">V</span>&gt;&gt; </span>&#123;</span><br><span class="line">        <span class="keyword">public</span> <span class="keyword">final</span> Map.<span class="function">Entry&lt;K,V&gt; <span class="title">next</span><span class="params">()</span> </span>&#123; <span class="keyword">return</span> nextNode(); &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/* ------------------------------------------------------------ */</span></span><br><span class="line">    <span class="comment">// spliterators</span></span><br><span class="line"></span><br><span class="line">    <span class="keyword">static</span> <span class="class"><span class="keyword">class</span> <span class="title">HashMapSpliterator</span>&lt;<span class="title">K</span>,<span class="title">V</span>&gt; </span>&#123;</span><br><span class="line">        <span class="keyword">final</span> HashMap&lt;K,V&gt; map;</span><br><span class="line">        Node&lt;K,V&gt; current;          <span class="comment">// current node</span></span><br><span class="line">        <span class="keyword">int</span> index;                  <span class="comment">// current index, modified on advance/split</span></span><br><span class="line">        <span class="keyword">int</span> fence;                  <span class="comment">// one past last index</span></span><br><span class="line">        <span class="keyword">int</span> est;                    <span class="comment">// size estimate</span></span><br><span class="line">        <span class="keyword">int</span> expectedModCount;       <span class="comment">// for comodification checks</span></span><br><span class="line"></span><br><span class="line">        HashMapSpliterator(HashMap&lt;K,V&gt; m, <span class="keyword">int</span> origin,</span><br><span class="line">                           <span class="keyword">int</span> fence, <span class="keyword">int</span> est,</span><br><span class="line">                           <span class="keyword">int</span> expectedModCount) &#123;</span><br><span class="line">            <span class="keyword">this</span>.map = m;</span><br><span class="line">            <span class="keyword">this</span>.index = origin;</span><br><span class="line">            <span class="keyword">this</span>.fence = fence;</span><br><span class="line">            <span class="keyword">this</span>.est = est;</span><br><span class="line">            <span class="keyword">this</span>.expectedModCount = expectedModCount;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">final</span> <span class="keyword">int</span> <span class="title">getFence</span><span class="params">()</span> </span>&#123; <span class="comment">// initialize fence and size on first use</span></span><br><span class="line">            <span class="keyword">int</span> hi;</span><br><span class="line">            <span class="keyword">if</span> ((hi = fence) &lt; <span class="number">0</span>) &#123;</span><br><span class="line">                HashMap&lt;K,V&gt; m = map;</span><br><span class="line">                est = m.size;</span><br><span class="line">                expectedModCount = m.modCount;</span><br><span class="line">                Node&lt;K,V&gt;[] tab = m.table;</span><br><span class="line">                hi = fence = (tab == <span class="keyword">null</span>) ? <span class="number">0</span> : tab.length;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">return</span> hi;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">final</span> <span class="keyword">long</span> <span class="title">estimateSize</span><span class="params">()</span> </span>&#123;</span><br><span class="line">            getFence(); <span class="comment">// force init</span></span><br><span class="line">            <span class="keyword">return</span> (<span class="keyword">long</span>) est;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">static</span> <span class="keyword">final</span> <span class="class"><span class="keyword">class</span> <span class="title">KeySpliterator</span>&lt;<span class="title">K</span>,<span class="title">V</span>&gt;</span></span><br><span class="line"><span class="class">        <span class="keyword">extends</span> <span class="title">HashMapSpliterator</span>&lt;<span class="title">K</span>,<span class="title">V</span>&gt;</span></span><br><span class="line"><span class="class">        <span class="keyword">implements</span> <span class="title">Spliterator</span>&lt;<span class="title">K</span>&gt; </span>&#123;</span><br><span class="line">        KeySpliterator(HashMap&lt;K,V&gt; m, <span class="keyword">int</span> origin, <span class="keyword">int</span> fence, <span class="keyword">int</span> est,</span><br><span class="line">                       <span class="keyword">int</span> expectedModCount) &#123;</span><br><span class="line">            <span class="keyword">super</span>(m, origin, fence, est, expectedModCount);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> KeySpliterator&lt;K,V&gt; <span class="title">trySplit</span><span class="params">()</span> </span>&#123;</span><br><span class="line">            <span class="keyword">int</span> hi = getFence(), lo = index, mid = (lo + hi) &gt;&gt;&gt; <span class="number">1</span>;</span><br><span class="line">            <span class="keyword">return</span> (lo &gt;= mid || current != <span class="keyword">null</span>) ? <span class="keyword">null</span> :</span><br><span class="line">                <span class="keyword">new</span> KeySpliterator&lt;&gt;(map, lo, index = mid, est &gt;&gt;&gt;= <span class="number">1</span>,</span><br><span class="line">                                        expectedModCount);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">forEachRemaining</span><span class="params">(Consumer&lt;? <span class="keyword">super</span> K&gt; action)</span> </span>&#123;</span><br><span class="line">            <span class="keyword">int</span> i, hi, mc;</span><br><span class="line">            <span class="keyword">if</span> (action == <span class="keyword">null</span>)</span><br><span class="line">                <span class="keyword">throw</span> <span class="keyword">new</span> NullPointerException();</span><br><span class="line">            HashMap&lt;K,V&gt; m = map;</span><br><span class="line">            Node&lt;K,V&gt;[] tab = m.table;</span><br><span class="line">            <span class="keyword">if</span> ((hi = fence) &lt; <span class="number">0</span>) &#123;</span><br><span class="line">                mc = expectedModCount = m.modCount;</span><br><span class="line">                hi = fence = (tab == <span class="keyword">null</span>) ? <span class="number">0</span> : tab.length;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">else</span></span><br><span class="line">                mc = expectedModCount;</span><br><span class="line">            <span class="keyword">if</span> (tab != <span class="keyword">null</span> &amp;&amp; tab.length &gt;= hi &amp;&amp;</span><br><span class="line">                (i = index) &gt;= <span class="number">0</span> &amp;&amp; (i &lt; (index = hi) || current != <span class="keyword">null</span>)) &#123;</span><br><span class="line">                Node&lt;K,V&gt; p = current;</span><br><span class="line">                current = <span class="keyword">null</span>;</span><br><span class="line">                <span class="keyword">do</span> &#123;</span><br><span class="line">                    <span class="keyword">if</span> (p == <span class="keyword">null</span>)</span><br><span class="line">                        p = tab[i++];</span><br><span class="line">                    <span class="keyword">else</span> &#123;</span><br><span class="line">                        action.accept(p.key);</span><br><span class="line">                        p = p.next;</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125; <span class="keyword">while</span> (p != <span class="keyword">null</span> || i &lt; hi);</span><br><span class="line">                <span class="keyword">if</span> (m.modCount != mc)</span><br><span class="line">                    <span class="keyword">throw</span> <span class="keyword">new</span> ConcurrentModificationException();</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">tryAdvance</span><span class="params">(Consumer&lt;? <span class="keyword">super</span> K&gt; action)</span> </span>&#123;</span><br><span class="line">            <span class="keyword">int</span> hi;</span><br><span class="line">            <span class="keyword">if</span> (action == <span class="keyword">null</span>)</span><br><span class="line">                <span class="keyword">throw</span> <span class="keyword">new</span> NullPointerException();</span><br><span class="line">            Node&lt;K,V&gt;[] tab = map.table;</span><br><span class="line">            <span class="keyword">if</span> (tab != <span class="keyword">null</span> &amp;&amp; tab.length &gt;= (hi = getFence()) &amp;&amp; index &gt;= <span class="number">0</span>) &#123;</span><br><span class="line">                <span class="keyword">while</span> (current != <span class="keyword">null</span> || index &lt; hi) &#123;</span><br><span class="line">                    <span class="keyword">if</span> (current == <span class="keyword">null</span>)</span><br><span class="line">                        current = tab[index++];</span><br><span class="line">                    <span class="keyword">else</span> &#123;</span><br><span class="line">                        K k = current.key;</span><br><span class="line">                        current = current.next;</span><br><span class="line">                        action.accept(k);</span><br><span class="line">                        <span class="keyword">if</span> (map.modCount != expectedModCount)</span><br><span class="line">                            <span class="keyword">throw</span> <span class="keyword">new</span> ConcurrentModificationException();</span><br><span class="line">                        <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">characteristics</span><span class="params">()</span> </span>&#123;</span><br><span class="line">            <span class="keyword">return</span> (fence &lt; <span class="number">0</span> || est == map.size ? Spliterator.SIZED : <span class="number">0</span>) |</span><br><span class="line">                Spliterator.DISTINCT;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">static</span> <span class="keyword">final</span> <span class="class"><span class="keyword">class</span> <span class="title">ValueSpliterator</span>&lt;<span class="title">K</span>,<span class="title">V</span>&gt;</span></span><br><span class="line"><span class="class">        <span class="keyword">extends</span> <span class="title">HashMapSpliterator</span>&lt;<span class="title">K</span>,<span class="title">V</span>&gt;</span></span><br><span class="line"><span class="class">        <span class="keyword">implements</span> <span class="title">Spliterator</span>&lt;<span class="title">V</span>&gt; </span>&#123;</span><br><span class="line">        ValueSpliterator(HashMap&lt;K,V&gt; m, <span class="keyword">int</span> origin, <span class="keyword">int</span> fence, <span class="keyword">int</span> est,</span><br><span class="line">                         <span class="keyword">int</span> expectedModCount) &#123;</span><br><span class="line">            <span class="keyword">super</span>(m, origin, fence, est, expectedModCount);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> ValueSpliterator&lt;K,V&gt; <span class="title">trySplit</span><span class="params">()</span> </span>&#123;</span><br><span class="line">            <span class="keyword">int</span> hi = getFence(), lo = index, mid = (lo + hi) &gt;&gt;&gt; <span class="number">1</span>;</span><br><span class="line">            <span class="keyword">return</span> (lo &gt;= mid || current != <span class="keyword">null</span>) ? <span class="keyword">null</span> :</span><br><span class="line">                <span class="keyword">new</span> ValueSpliterator&lt;&gt;(map, lo, index = mid, est &gt;&gt;&gt;= <span class="number">1</span>,</span><br><span class="line">                                          expectedModCount);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">forEachRemaining</span><span class="params">(Consumer&lt;? <span class="keyword">super</span> V&gt; action)</span> </span>&#123;</span><br><span class="line">            <span class="keyword">int</span> i, hi, mc;</span><br><span class="line">            <span class="keyword">if</span> (action == <span class="keyword">null</span>)</span><br><span class="line">                <span class="keyword">throw</span> <span class="keyword">new</span> NullPointerException();</span><br><span class="line">            HashMap&lt;K,V&gt; m = map;</span><br><span class="line">            Node&lt;K,V&gt;[] tab = m.table;</span><br><span class="line">            <span class="keyword">if</span> ((hi = fence) &lt; <span class="number">0</span>) &#123;</span><br><span class="line">                mc = expectedModCount = m.modCount;</span><br><span class="line">                hi = fence = (tab == <span class="keyword">null</span>) ? <span class="number">0</span> : tab.length;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">else</span></span><br><span class="line">                mc = expectedModCount;</span><br><span class="line">            <span class="keyword">if</span> (tab != <span class="keyword">null</span> &amp;&amp; tab.length &gt;= hi &amp;&amp;</span><br><span class="line">                (i = index) &gt;= <span class="number">0</span> &amp;&amp; (i &lt; (index = hi) || current != <span class="keyword">null</span>)) &#123;</span><br><span class="line">                Node&lt;K,V&gt; p = current;</span><br><span class="line">                current = <span class="keyword">null</span>;</span><br><span class="line">                <span class="keyword">do</span> &#123;</span><br><span class="line">                    <span class="keyword">if</span> (p == <span class="keyword">null</span>)</span><br><span class="line">                        p = tab[i++];</span><br><span class="line">                    <span class="keyword">else</span> &#123;</span><br><span class="line">                        action.accept(p.value);</span><br><span class="line">                        p = p.next;</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125; <span class="keyword">while</span> (p != <span class="keyword">null</span> || i &lt; hi);</span><br><span class="line">                <span class="keyword">if</span> (m.modCount != mc)</span><br><span class="line">                    <span class="keyword">throw</span> <span class="keyword">new</span> ConcurrentModificationException();</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">tryAdvance</span><span class="params">(Consumer&lt;? <span class="keyword">super</span> V&gt; action)</span> </span>&#123;</span><br><span class="line">            <span class="keyword">int</span> hi;</span><br><span class="line">            <span class="keyword">if</span> (action == <span class="keyword">null</span>)</span><br><span class="line">                <span class="keyword">throw</span> <span class="keyword">new</span> NullPointerException();</span><br><span class="line">            Node&lt;K,V&gt;[] tab = map.table;</span><br><span class="line">            <span class="keyword">if</span> (tab != <span class="keyword">null</span> &amp;&amp; tab.length &gt;= (hi = getFence()) &amp;&amp; index &gt;= <span class="number">0</span>) &#123;</span><br><span class="line">                <span class="keyword">while</span> (current != <span class="keyword">null</span> || index &lt; hi) &#123;</span><br><span class="line">                    <span class="keyword">if</span> (current == <span class="keyword">null</span>)</span><br><span class="line">                        current = tab[index++];</span><br><span class="line">                    <span class="keyword">else</span> &#123;</span><br><span class="line">                        V v = current.value;</span><br><span class="line">                        current = current.next;</span><br><span class="line">                        action.accept(v);</span><br><span class="line">                        <span class="keyword">if</span> (map.modCount != expectedModCount)</span><br><span class="line">                            <span class="keyword">throw</span> <span class="keyword">new</span> ConcurrentModificationException();</span><br><span class="line">                        <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">characteristics</span><span class="params">()</span> </span>&#123;</span><br><span class="line">            <span class="keyword">return</span> (fence &lt; <span class="number">0</span> || est == map.size ? Spliterator.SIZED : <span class="number">0</span>);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">static</span> <span class="keyword">final</span> <span class="class"><span class="keyword">class</span> <span class="title">EntrySpliterator</span>&lt;<span class="title">K</span>,<span class="title">V</span>&gt;</span></span><br><span class="line"><span class="class">        <span class="keyword">extends</span> <span class="title">HashMapSpliterator</span>&lt;<span class="title">K</span>,<span class="title">V</span>&gt;</span></span><br><span class="line"><span class="class">        <span class="keyword">implements</span> <span class="title">Spliterator</span>&lt;<span class="title">Map</span>.<span class="title">Entry</span>&lt;<span class="title">K</span>,<span class="title">V</span>&gt;&gt; </span>&#123;</span><br><span class="line">        EntrySpliterator(HashMap&lt;K,V&gt; m, <span class="keyword">int</span> origin, <span class="keyword">int</span> fence, <span class="keyword">int</span> est,</span><br><span class="line">                         <span class="keyword">int</span> expectedModCount) &#123;</span><br><span class="line">            <span class="keyword">super</span>(m, origin, fence, est, expectedModCount);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> EntrySpliterator&lt;K,V&gt; <span class="title">trySplit</span><span class="params">()</span> </span>&#123;</span><br><span class="line">            <span class="keyword">int</span> hi = getFence(), lo = index, mid = (lo + hi) &gt;&gt;&gt; <span class="number">1</span>;</span><br><span class="line">            <span class="keyword">return</span> (lo &gt;= mid || current != <span class="keyword">null</span>) ? <span class="keyword">null</span> :</span><br><span class="line">                <span class="keyword">new</span> EntrySpliterator&lt;&gt;(map, lo, index = mid, est &gt;&gt;&gt;= <span class="number">1</span>,</span><br><span class="line">                                          expectedModCount);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">forEachRemaining</span><span class="params">(Consumer&lt;? <span class="keyword">super</span> Map.Entry&lt;K,V&gt;&gt; action)</span> </span>&#123;</span><br><span class="line">            <span class="keyword">int</span> i, hi, mc;</span><br><span class="line">            <span class="keyword">if</span> (action == <span class="keyword">null</span>)</span><br><span class="line">                <span class="keyword">throw</span> <span class="keyword">new</span> NullPointerException();</span><br><span class="line">            HashMap&lt;K,V&gt; m = map;</span><br><span class="line">            Node&lt;K,V&gt;[] tab = m.table;</span><br><span class="line">            <span class="keyword">if</span> ((hi = fence) &lt; <span class="number">0</span>) &#123;</span><br><span class="line">                mc = expectedModCount = m.modCount;</span><br><span class="line">                hi = fence = (tab == <span class="keyword">null</span>) ? <span class="number">0</span> : tab.length;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">else</span></span><br><span class="line">                mc = expectedModCount;</span><br><span class="line">            <span class="keyword">if</span> (tab != <span class="keyword">null</span> &amp;&amp; tab.length &gt;= hi &amp;&amp;</span><br><span class="line">                (i = index) &gt;= <span class="number">0</span> &amp;&amp; (i &lt; (index = hi) || current != <span class="keyword">null</span>)) &#123;</span><br><span class="line">                Node&lt;K,V&gt; p = current;</span><br><span class="line">                current = <span class="keyword">null</span>;</span><br><span class="line">                <span class="keyword">do</span> &#123;</span><br><span class="line">                    <span class="keyword">if</span> (p == <span class="keyword">null</span>)</span><br><span class="line">                        p = tab[i++];</span><br><span class="line">                    <span class="keyword">else</span> &#123;</span><br><span class="line">                        action.accept(p);</span><br><span class="line">                        p = p.next;</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125; <span class="keyword">while</span> (p != <span class="keyword">null</span> || i &lt; hi);</span><br><span class="line">                <span class="keyword">if</span> (m.modCount != mc)</span><br><span class="line">                    <span class="keyword">throw</span> <span class="keyword">new</span> ConcurrentModificationException();</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">tryAdvance</span><span class="params">(Consumer&lt;? <span class="keyword">super</span> Map.Entry&lt;K,V&gt;&gt; action)</span> </span>&#123;</span><br><span class="line">            <span class="keyword">int</span> hi;</span><br><span class="line">            <span class="keyword">if</span> (action == <span class="keyword">null</span>)</span><br><span class="line">                <span class="keyword">throw</span> <span class="keyword">new</span> NullPointerException();</span><br><span class="line">            Node&lt;K,V&gt;[] tab = map.table;</span><br><span class="line">            <span class="keyword">if</span> (tab != <span class="keyword">null</span> &amp;&amp; tab.length &gt;= (hi = getFence()) &amp;&amp; index &gt;= <span class="number">0</span>) &#123;</span><br><span class="line">                <span class="keyword">while</span> (current != <span class="keyword">null</span> || index &lt; hi) &#123;</span><br><span class="line">                    <span class="keyword">if</span> (current == <span class="keyword">null</span>)</span><br><span class="line">                        current = tab[index++];</span><br><span class="line">                    <span class="keyword">else</span> &#123;</span><br><span class="line">                        Node&lt;K,V&gt; e = current;</span><br><span class="line">                        current = current.next;</span><br><span class="line">                        action.accept(e);</span><br><span class="line">                        <span class="keyword">if</span> (map.modCount != expectedModCount)</span><br><span class="line">                            <span class="keyword">throw</span> <span class="keyword">new</span> ConcurrentModificationException();</span><br><span class="line">                        <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">characteristics</span><span class="params">()</span> </span>&#123;</span><br><span class="line">            <span class="keyword">return</span> (fence &lt; <span class="number">0</span> || est == map.size ? Spliterator.SIZED : <span class="number">0</span>) |</span><br><span class="line">                Spliterator.DISTINCT;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/* ------------------------------------------------------------ */</span></span><br><span class="line">    <span class="comment">// LinkedHashMap support</span></span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="comment">/*</span></span><br><span class="line"><span class="comment">     * The following package-protected methods are designed to be</span></span><br><span class="line"><span class="comment">     * overridden by LinkedHashMap, but not by any other subclass.</span></span><br><span class="line"><span class="comment">     * Nearly all other internal methods are also package-protected</span></span><br><span class="line"><span class="comment">     * but are declared final, so can be used by LinkedHashMap, view</span></span><br><span class="line"><span class="comment">     * classes, and HashSet.</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line"></span><br><span class="line">    <span class="comment">// Create a regular (non-tree) node</span></span><br><span class="line">    <span class="function">Node&lt;K,V&gt; <span class="title">newNode</span><span class="params">(<span class="keyword">int</span> hash, K key, V value, Node&lt;K,V&gt; next)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">new</span> Node&lt;&gt;(hash, key, value, next);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// For conversion from TreeNodes to plain nodes</span></span><br><span class="line">    <span class="function">Node&lt;K,V&gt; <span class="title">replacementNode</span><span class="params">(Node&lt;K,V&gt; p, Node&lt;K,V&gt; next)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">new</span> Node&lt;&gt;(p.hash, p.key, p.value, next);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// Create a tree bin node</span></span><br><span class="line">    <span class="function">TreeNode&lt;K,V&gt; <span class="title">newTreeNode</span><span class="params">(<span class="keyword">int</span> hash, K key, V value, Node&lt;K,V&gt; next)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">new</span> TreeNode&lt;&gt;(hash, key, value, next);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// For treeifyBin</span></span><br><span class="line">    <span class="function">TreeNode&lt;K,V&gt; <span class="title">replacementTreeNode</span><span class="params">(Node&lt;K,V&gt; p, Node&lt;K,V&gt; next)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">new</span> TreeNode&lt;&gt;(p.hash, p.key, p.value, next);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * Reset to initial default state.  Called by clone and readObject.</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">reinitialize</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        table = <span class="keyword">null</span>;</span><br><span class="line">        entrySet = <span class="keyword">null</span>;</span><br><span class="line">        keySet = <span class="keyword">null</span>;</span><br><span class="line">        values = <span class="keyword">null</span>;</span><br><span class="line">        modCount = <span class="number">0</span>;</span><br><span class="line">        threshold = <span class="number">0</span>;</span><br><span class="line">        size = <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// Callbacks to allow LinkedHashMap post-actions</span></span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">afterNodeAccess</span><span class="params">(Node&lt;K,V&gt; p)</span> </span>&#123; &#125;</span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">afterNodeInsertion</span><span class="params">(<span class="keyword">boolean</span> evict)</span> </span>&#123; &#125;</span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">afterNodeRemoval</span><span class="params">(Node&lt;K,V&gt; p)</span> </span>&#123; &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// Called only from writeObject, to ensure compatible ordering.</span></span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">internalWriteEntries</span><span class="params">(java.io.ObjectOutputStream s)</span> <span class="keyword">throws</span> IOException </span>&#123;</span><br><span class="line">        Node&lt;K,V&gt;[] tab;</span><br><span class="line">        <span class="keyword">if</span> (size &gt; <span class="number">0</span> &amp;&amp; (tab = table) != <span class="keyword">null</span>) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; tab.length; ++i) &#123;</span><br><span class="line">                <span class="keyword">for</span> (Node&lt;K,V&gt; e = tab[i]; e != <span class="keyword">null</span>; e = e.next) &#123;</span><br><span class="line">                    s.writeObject(e.key);</span><br><span class="line">                    s.writeObject(e.value);</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/* ------------------------------------------------------------ */</span></span><br><span class="line">    <span class="comment">// Tree bins</span></span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn</span></span><br><span class="line"><span class="comment">     * extends Node) so can be used as extension of either regular or</span></span><br><span class="line"><span class="comment">     * linked node.</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="keyword">static</span> <span class="keyword">final</span> <span class="class"><span class="keyword">class</span> <span class="title">TreeNode</span>&lt;<span class="title">K</span>,<span class="title">V</span>&gt; <span class="keyword">extends</span> <span class="title">LinkedHashMap</span>.<span class="title">Entry</span>&lt;<span class="title">K</span>,<span class="title">V</span>&gt; </span>&#123;</span><br><span class="line">        TreeNode&lt;K,V&gt; parent;  <span class="comment">// red-black tree links</span></span><br><span class="line">        TreeNode&lt;K,V&gt; left;</span><br><span class="line">        TreeNode&lt;K,V&gt; right;</span><br><span class="line">        TreeNode&lt;K,V&gt; prev;    <span class="comment">// needed to unlink next upon deletion</span></span><br><span class="line">        <span class="keyword">boolean</span> red;</span><br><span class="line">        TreeNode(<span class="keyword">int</span> hash, K key, V val, Node&lt;K,V&gt; next) &#123;</span><br><span class="line">            <span class="keyword">super</span>(hash, key, val, next);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">/**</span></span><br><span class="line"><span class="comment">         * Returns root of tree containing this node.</span></span><br><span class="line"><span class="comment">         */</span></span><br><span class="line">        <span class="function"><span class="keyword">final</span> TreeNode&lt;K,V&gt; <span class="title">root</span><span class="params">()</span> </span>&#123;</span><br><span class="line">            <span class="keyword">for</span> (TreeNode&lt;K,V&gt; r = <span class="keyword">this</span>, p;;) &#123;</span><br><span class="line">                <span class="keyword">if</span> ((p = r.parent) == <span class="keyword">null</span>)</span><br><span class="line">                    <span class="keyword">return</span> r;</span><br><span class="line">                r = p;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">/**</span></span><br><span class="line"><span class="comment">         * Ensures that the given root is the first node of its bin.</span></span><br><span class="line"><span class="comment">         */</span></span><br><span class="line">        <span class="keyword">static</span> &lt;K,V&gt; <span class="function"><span class="keyword">void</span> <span class="title">moveRootToFront</span><span class="params">(Node&lt;K,V&gt;[] tab, TreeNode&lt;K,V&gt; root)</span> </span>&#123;</span><br><span class="line">            <span class="keyword">int</span> n;</span><br><span class="line">            <span class="keyword">if</span> (root != <span class="keyword">null</span> &amp;&amp; tab != <span class="keyword">null</span> &amp;&amp; (n = tab.length) &gt; <span class="number">0</span>) &#123;</span><br><span class="line">                <span class="keyword">int</span> index = (n - <span class="number">1</span>) &amp; root.hash;</span><br><span class="line">                TreeNode&lt;K,V&gt; first = (TreeNode&lt;K,V&gt;)tab[index];</span><br><span class="line">                <span class="keyword">if</span> (root != first) &#123;</span><br><span class="line">                    Node&lt;K,V&gt; rn;</span><br><span class="line">                    tab[index] = root;</span><br><span class="line">                    TreeNode&lt;K,V&gt; rp = root.prev;</span><br><span class="line">                    <span class="keyword">if</span> ((rn = root.next) != <span class="keyword">null</span>)</span><br><span class="line">                        ((TreeNode&lt;K,V&gt;)rn).prev = rp;</span><br><span class="line">                    <span class="keyword">if</span> (rp != <span class="keyword">null</span>)</span><br><span class="line">                        rp.next = rn;</span><br><span class="line">                    <span class="keyword">if</span> (first != <span class="keyword">null</span>)</span><br><span class="line">                        first.prev = root;</span><br><span class="line">                    root.next = first;</span><br><span class="line">                    root.prev = <span class="keyword">null</span>;</span><br><span class="line">                &#125;</span><br><span class="line">                <span class="function"><span class="keyword">assert</span> <span class="title">checkInvariants</span><span class="params">(root)</span></span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">/**</span></span><br><span class="line"><span class="comment">         * Finds the node starting at root p with the given hash and key.</span></span><br><span class="line"><span class="comment">         * The kc argument caches comparableClassFor(key) upon first use</span></span><br><span class="line"><span class="comment">         * comparing keys.</span></span><br><span class="line"><span class="comment">         */</span></span><br><span class="line">        <span class="function"><span class="keyword">final</span> TreeNode&lt;K,V&gt; <span class="title">find</span><span class="params">(<span class="keyword">int</span> h, Object k, Class&lt;?&gt; kc)</span> </span>&#123;</span><br><span class="line">            TreeNode&lt;K,V&gt; p = <span class="keyword">this</span>;</span><br><span class="line">            <span class="keyword">do</span> &#123;</span><br><span class="line">                <span class="keyword">int</span> ph, dir; K pk;</span><br><span class="line">                TreeNode&lt;K,V&gt; pl = p.left, pr = p.right, q;</span><br><span class="line">                <span class="keyword">if</span> ((ph = p.hash) &gt; h)</span><br><span class="line">                    p = pl;</span><br><span class="line">                <span class="keyword">else</span> <span class="keyword">if</span> (ph &lt; h)</span><br><span class="line">                    p = pr;</span><br><span class="line">                <span class="keyword">else</span> <span class="keyword">if</span> ((pk = p.key) == k || (k != <span class="keyword">null</span> &amp;&amp; k.equals(pk)))</span><br><span class="line">                    <span class="keyword">return</span> p;</span><br><span class="line">                <span class="keyword">else</span> <span class="keyword">if</span> (pl == <span class="keyword">null</span>)</span><br><span class="line">                    p = pr;</span><br><span class="line">                <span class="keyword">else</span> <span class="keyword">if</span> (pr == <span class="keyword">null</span>)</span><br><span class="line">                    p = pl;</span><br><span class="line">                <span class="keyword">else</span> <span class="keyword">if</span> ((kc != <span class="keyword">null</span> ||</span><br><span class="line">                          (kc = comparableClassFor(k)) != <span class="keyword">null</span>) &amp;&amp;</span><br><span class="line">                         (dir = compareComparables(kc, k, pk)) != <span class="number">0</span>)</span><br><span class="line">                    p = (dir &lt; <span class="number">0</span>) ? pl : pr;</span><br><span class="line">                <span class="keyword">else</span> <span class="keyword">if</span> ((q = pr.find(h, k, kc)) != <span class="keyword">null</span>)</span><br><span class="line">                    <span class="keyword">return</span> q;</span><br><span class="line">                <span class="keyword">else</span></span><br><span class="line">                    p = pl;</span><br><span class="line">            &#125; <span class="keyword">while</span> (p != <span class="keyword">null</span>);</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">/**</span></span><br><span class="line"><span class="comment">         * Calls find for root node.</span></span><br><span class="line"><span class="comment">         */</span></span><br><span class="line">        <span class="function"><span class="keyword">final</span> TreeNode&lt;K,V&gt; <span class="title">getTreeNode</span><span class="params">(<span class="keyword">int</span> h, Object k)</span> </span>&#123;</span><br><span class="line">            <span class="keyword">return</span> ((parent != <span class="keyword">null</span>) ? root() : <span class="keyword">this</span>).find(h, k, <span class="keyword">null</span>);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">/**</span></span><br><span class="line"><span class="comment">         * Tie-breaking utility for ordering insertions when equal</span></span><br><span class="line"><span class="comment">         * hashCodes and non-comparable. We don&#x27;t require a total</span></span><br><span class="line"><span class="comment">         * order, just a consistent insertion rule to maintain</span></span><br><span class="line"><span class="comment">         * equivalence across rebalancings. Tie-breaking further than</span></span><br><span class="line"><span class="comment">         * necessary simplifies testing a bit.</span></span><br><span class="line"><span class="comment">         */</span></span><br><span class="line">        <span class="function"><span class="keyword">static</span> <span class="keyword">int</span> <span class="title">tieBreakOrder</span><span class="params">(Object a, Object b)</span> </span>&#123;</span><br><span class="line">            <span class="keyword">int</span> d;</span><br><span class="line">            <span class="keyword">if</span> (a == <span class="keyword">null</span> || b == <span class="keyword">null</span> ||</span><br><span class="line">                (d = a.getClass().getName().</span><br><span class="line">                 compareTo(b.getClass().getName())) == <span class="number">0</span>)</span><br><span class="line">                d = (System.identityHashCode(a) &lt;= System.identityHashCode(b) ?</span><br><span class="line">                     -<span class="number">1</span> : <span class="number">1</span>);</span><br><span class="line">            <span class="keyword">return</span> d;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">/**</span></span><br><span class="line"><span class="comment">         * Forms tree of the nodes linked from this node.</span></span><br><span class="line"><span class="comment">         * <span class="doctag">@return</span> root of tree</span></span><br><span class="line"><span class="comment">         */</span></span><br><span class="line">        <span class="function"><span class="keyword">final</span> <span class="keyword">void</span> <span class="title">treeify</span><span class="params">(Node&lt;K,V&gt;[] tab)</span> </span>&#123;</span><br><span class="line">            TreeNode&lt;K,V&gt; root = <span class="keyword">null</span>;</span><br><span class="line">            <span class="keyword">for</span> (TreeNode&lt;K,V&gt; x = <span class="keyword">this</span>, next; x != <span class="keyword">null</span>; x = next) &#123;</span><br><span class="line">                next = (TreeNode&lt;K,V&gt;)x.next;</span><br><span class="line">                x.left = x.right = <span class="keyword">null</span>;</span><br><span class="line">                <span class="keyword">if</span> (root == <span class="keyword">null</span>) &#123;</span><br><span class="line">                    x.parent = <span class="keyword">null</span>;</span><br><span class="line">                    x.red = <span class="keyword">false</span>;</span><br><span class="line">                    root = x;</span><br><span class="line">                &#125;</span><br><span class="line">                <span class="keyword">else</span> &#123;</span><br><span class="line">                    K k = x.key;</span><br><span class="line">                    <span class="keyword">int</span> h = x.hash;</span><br><span class="line">                    Class&lt;?&gt; kc = <span class="keyword">null</span>;</span><br><span class="line">                    <span class="keyword">for</span> (TreeNode&lt;K,V&gt; p = root;;) &#123;</span><br><span class="line">                        <span class="keyword">int</span> dir, ph;</span><br><span class="line">                        K pk = p.key;</span><br><span class="line">                        <span class="keyword">if</span> ((ph = p.hash) &gt; h)</span><br><span class="line">                            dir = -<span class="number">1</span>;</span><br><span class="line">                        <span class="keyword">else</span> <span class="keyword">if</span> (ph &lt; h)</span><br><span class="line">                            dir = <span class="number">1</span>;</span><br><span class="line">                        <span class="keyword">else</span> <span class="keyword">if</span> ((kc == <span class="keyword">null</span> &amp;&amp;</span><br><span class="line">                                  (kc = comparableClassFor(k)) == <span class="keyword">null</span>) ||</span><br><span class="line">                                 (dir = compareComparables(kc, k, pk)) == <span class="number">0</span>)</span><br><span class="line">                            dir = tieBreakOrder(k, pk);</span><br><span class="line"></span><br><span class="line">                        TreeNode&lt;K,V&gt; xp = p;</span><br><span class="line">                        <span class="keyword">if</span> ((p = (dir &lt;= <span class="number">0</span>) ? p.left : p.right) == <span class="keyword">null</span>) &#123;</span><br><span class="line">                            x.parent = xp;</span><br><span class="line">                            <span class="keyword">if</span> (dir &lt;= <span class="number">0</span>)</span><br><span class="line">                                xp.left = x;</span><br><span class="line">                            <span class="keyword">else</span></span><br><span class="line">                                xp.right = x;</span><br><span class="line">                            root = balanceInsertion(root, x);</span><br><span class="line">                            <span class="keyword">break</span>;</span><br><span class="line">                        &#125;</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">            moveRootToFront(tab, root);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">/**</span></span><br><span class="line"><span class="comment">         * Returns a list of non-TreeNodes replacing those linked from</span></span><br><span class="line"><span class="comment">         * this node.</span></span><br><span class="line"><span class="comment">         */</span></span><br><span class="line">        <span class="function"><span class="keyword">final</span> Node&lt;K,V&gt; <span class="title">untreeify</span><span class="params">(HashMap&lt;K,V&gt; map)</span> </span>&#123;</span><br><span class="line">            Node&lt;K,V&gt; hd = <span class="keyword">null</span>, tl = <span class="keyword">null</span>;</span><br><span class="line">            <span class="keyword">for</span> (Node&lt;K,V&gt; q = <span class="keyword">this</span>; q != <span class="keyword">null</span>; q = q.next) &#123;</span><br><span class="line">                Node&lt;K,V&gt; p = map.replacementNode(q, <span class="keyword">null</span>);</span><br><span class="line">                <span class="keyword">if</span> (tl == <span class="keyword">null</span>)</span><br><span class="line">                    hd = p;</span><br><span class="line">                <span class="keyword">else</span></span><br><span class="line">                    tl.next = p;</span><br><span class="line">                tl = p;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">return</span> hd;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">/**</span></span><br><span class="line"><span class="comment">         * Tree version of putVal.</span></span><br><span class="line"><span class="comment">         */</span></span><br><span class="line">        <span class="function"><span class="keyword">final</span> TreeNode&lt;K,V&gt; <span class="title">putTreeVal</span><span class="params">(HashMap&lt;K,V&gt; map, Node&lt;K,V&gt;[] tab,</span></span></span><br><span class="line"><span class="function"><span class="params">                                       <span class="keyword">int</span> h, K k, V v)</span> </span>&#123;</span><br><span class="line">            Class&lt;?&gt; kc = <span class="keyword">null</span>;</span><br><span class="line">            <span class="keyword">boolean</span> searched = <span class="keyword">false</span>;</span><br><span class="line">            TreeNode&lt;K,V&gt; root = (parent != <span class="keyword">null</span>) ? root() : <span class="keyword">this</span>;</span><br><span class="line">            <span class="keyword">for</span> (TreeNode&lt;K,V&gt; p = root;;) &#123;</span><br><span class="line">                <span class="keyword">int</span> dir, ph; K pk;</span><br><span class="line">                <span class="keyword">if</span> ((ph = p.hash) &gt; h)</span><br><span class="line">                    dir = -<span class="number">1</span>;</span><br><span class="line">                <span class="keyword">else</span> <span class="keyword">if</span> (ph &lt; h)</span><br><span class="line">                    dir = <span class="number">1</span>;</span><br><span class="line">                <span class="keyword">else</span> <span class="keyword">if</span> ((pk = p.key) == k || (k != <span class="keyword">null</span> &amp;&amp; k.equals(pk)))</span><br><span class="line">                    <span class="keyword">return</span> p;</span><br><span class="line">                <span class="keyword">else</span> <span class="keyword">if</span> ((kc == <span class="keyword">null</span> &amp;&amp;</span><br><span class="line">                          (kc = comparableClassFor(k)) == <span class="keyword">null</span>) ||</span><br><span class="line">                         (dir = compareComparables(kc, k, pk)) == <span class="number">0</span>) &#123;</span><br><span class="line">                    <span class="keyword">if</span> (!searched) &#123;</span><br><span class="line">                        TreeNode&lt;K,V&gt; q, ch;</span><br><span class="line">                        searched = <span class="keyword">true</span>;</span><br><span class="line">                        <span class="keyword">if</span> (((ch = p.left) != <span class="keyword">null</span> &amp;&amp;</span><br><span class="line">                             (q = ch.find(h, k, kc)) != <span class="keyword">null</span>) ||</span><br><span class="line">                            ((ch = p.right) != <span class="keyword">null</span> &amp;&amp;</span><br><span class="line">                             (q = ch.find(h, k, kc)) != <span class="keyword">null</span>))</span><br><span class="line">                            <span class="keyword">return</span> q;</span><br><span class="line">                    &#125;</span><br><span class="line">                    dir = tieBreakOrder(k, pk);</span><br><span class="line">                &#125;</span><br><span class="line"></span><br><span class="line">                TreeNode&lt;K,V&gt; xp = p;</span><br><span class="line">                <span class="keyword">if</span> ((p = (dir &lt;= <span class="number">0</span>) ? p.left : p.right) == <span class="keyword">null</span>) &#123;</span><br><span class="line">                    Node&lt;K,V&gt; xpn = xp.next;</span><br><span class="line">                    TreeNode&lt;K,V&gt; x = map.newTreeNode(h, k, v, xpn);</span><br><span class="line">                    <span class="keyword">if</span> (dir &lt;= <span class="number">0</span>)</span><br><span class="line">                        xp.left = x;</span><br><span class="line">                    <span class="keyword">else</span></span><br><span class="line">                        xp.right = x;</span><br><span class="line">                    xp.next = x;</span><br><span class="line">                    x.parent = x.prev = xp;</span><br><span class="line">                    <span class="keyword">if</span> (xpn != <span class="keyword">null</span>)</span><br><span class="line">                        ((TreeNode&lt;K,V&gt;)xpn).prev = x;</span><br><span class="line">                    moveRootToFront(tab, balanceInsertion(root, x));</span><br><span class="line">                    <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">/**</span></span><br><span class="line"><span class="comment">         * Removes the given node, that must be present before this call.</span></span><br><span class="line"><span class="comment">         * This is messier than typical red-black deletion code because we</span></span><br><span class="line"><span class="comment">         * cannot swap the contents of an interior node with a leaf</span></span><br><span class="line"><span class="comment">         * successor that is pinned by &quot;next&quot; pointers that are accessible</span></span><br><span class="line"><span class="comment">         * independently during traversal. So instead we swap the tree</span></span><br><span class="line"><span class="comment">         * linkages. If the current tree appears to have too few nodes,</span></span><br><span class="line"><span class="comment">         * the bin is converted back to a plain bin. (The test triggers</span></span><br><span class="line"><span class="comment">         * somewhere between 2 and 6 nodes, depending on tree structure).</span></span><br><span class="line"><span class="comment">         */</span></span><br><span class="line">        <span class="function"><span class="keyword">final</span> <span class="keyword">void</span> <span class="title">removeTreeNode</span><span class="params">(HashMap&lt;K,V&gt; map, Node&lt;K,V&gt;[] tab,</span></span></span><br><span class="line"><span class="function"><span class="params">                                  <span class="keyword">boolean</span> movable)</span> </span>&#123;</span><br><span class="line">            <span class="keyword">int</span> n;</span><br><span class="line">            <span class="keyword">if</span> (tab == <span class="keyword">null</span> || (n = tab.length) == <span class="number">0</span>)</span><br><span class="line">                <span class="keyword">return</span>;</span><br><span class="line">            <span class="keyword">int</span> index = (n - <span class="number">1</span>) &amp; hash;</span><br><span class="line">            TreeNode&lt;K,V&gt; first = (TreeNode&lt;K,V&gt;)tab[index], root = first, rl;</span><br><span class="line">            TreeNode&lt;K,V&gt; succ = (TreeNode&lt;K,V&gt;)next, pred = prev;</span><br><span class="line">            <span class="keyword">if</span> (pred == <span class="keyword">null</span>)</span><br><span class="line">                tab[index] = first = succ;</span><br><span class="line">            <span class="keyword">else</span></span><br><span class="line">                pred.next = succ;</span><br><span class="line">            <span class="keyword">if</span> (succ != <span class="keyword">null</span>)</span><br><span class="line">                succ.prev = pred;</span><br><span class="line">            <span class="keyword">if</span> (first == <span class="keyword">null</span>)</span><br><span class="line">                <span class="keyword">return</span>;</span><br><span class="line">            <span class="keyword">if</span> (root.parent != <span class="keyword">null</span>)</span><br><span class="line">                root = root.root();</span><br><span class="line">            <span class="keyword">if</span> (root == <span class="keyword">null</span> || root.right == <span class="keyword">null</span> ||</span><br><span class="line">                (rl = root.left) == <span class="keyword">null</span> || rl.left == <span class="keyword">null</span>) &#123;</span><br><span class="line">                tab[index] = first.untreeify(map);  <span class="comment">// too small</span></span><br><span class="line">                <span class="keyword">return</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            TreeNode&lt;K,V&gt; p = <span class="keyword">this</span>, pl = left, pr = right, replacement;</span><br><span class="line">            <span class="keyword">if</span> (pl != <span class="keyword">null</span> &amp;&amp; pr != <span class="keyword">null</span>) &#123;</span><br><span class="line">                TreeNode&lt;K,V&gt; s = pr, sl;</span><br><span class="line">                <span class="keyword">while</span> ((sl = s.left) != <span class="keyword">null</span>) <span class="comment">// find successor</span></span><br><span class="line">                    s = sl;</span><br><span class="line">                <span class="keyword">boolean</span> c = s.red; s.red = p.red; p.red = c; <span class="comment">// swap colors</span></span><br><span class="line">                TreeNode&lt;K,V&gt; sr = s.right;</span><br><span class="line">                TreeNode&lt;K,V&gt; pp = p.parent;</span><br><span class="line">                <span class="keyword">if</span> (s == pr) &#123; <span class="comment">// p was s&#x27;s direct parent</span></span><br><span class="line">                    p.parent = s;</span><br><span class="line">                    s.right = p;</span><br><span class="line">                &#125;</span><br><span class="line">                <span class="keyword">else</span> &#123;</span><br><span class="line">                    TreeNode&lt;K,V&gt; sp = s.parent;</span><br><span class="line">                    <span class="keyword">if</span> ((p.parent = sp) != <span class="keyword">null</span>) &#123;</span><br><span class="line">                        <span class="keyword">if</span> (s == sp.left)</span><br><span class="line">                            sp.left = p;</span><br><span class="line">                        <span class="keyword">else</span></span><br><span class="line">                            sp.right = p;</span><br><span class="line">                    &#125;</span><br><span class="line">                    <span class="keyword">if</span> ((s.right = pr) != <span class="keyword">null</span>)</span><br><span class="line">                        pr.parent = s;</span><br><span class="line">                &#125;</span><br><span class="line">                p.left = <span class="keyword">null</span>;</span><br><span class="line">                <span class="keyword">if</span> ((p.right = sr) != <span class="keyword">null</span>)</span><br><span class="line">                    sr.parent = p;</span><br><span class="line">                <span class="keyword">if</span> ((s.left = pl) != <span class="keyword">null</span>)</span><br><span class="line">                    pl.parent = s;</span><br><span class="line">                <span class="keyword">if</span> ((s.parent = pp) == <span class="keyword">null</span>)</span><br><span class="line">                    root = s;</span><br><span class="line">                <span class="keyword">else</span> <span class="keyword">if</span> (p == pp.left)</span><br><span class="line">                    pp.left = s;</span><br><span class="line">                <span class="keyword">else</span></span><br><span class="line">                    pp.right = s;</span><br><span class="line">                <span class="keyword">if</span> (sr != <span class="keyword">null</span>)</span><br><span class="line">                    replacement = sr;</span><br><span class="line">                <span class="keyword">else</span></span><br><span class="line">                    replacement = p;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">else</span> <span class="keyword">if</span> (pl != <span class="keyword">null</span>)</span><br><span class="line">                replacement = pl;</span><br><span class="line">            <span class="keyword">else</span> <span class="keyword">if</span> (pr != <span class="keyword">null</span>)</span><br><span class="line">                replacement = pr;</span><br><span class="line">            <span class="keyword">else</span></span><br><span class="line">                replacement = p;</span><br><span class="line">            <span class="keyword">if</span> (replacement != p) &#123;</span><br><span class="line">                TreeNode&lt;K,V&gt; pp = replacement.parent = p.parent;</span><br><span class="line">                <span class="keyword">if</span> (pp == <span class="keyword">null</span>)</span><br><span class="line">                    root = replacement;</span><br><span class="line">                <span class="keyword">else</span> <span class="keyword">if</span> (p == pp.left)</span><br><span class="line">                    pp.left = replacement;</span><br><span class="line">                <span class="keyword">else</span></span><br><span class="line">                    pp.right = replacement;</span><br><span class="line">                p.left = p.right = p.parent = <span class="keyword">null</span>;</span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line">            TreeNode&lt;K,V&gt; r = p.red ? root : balanceDeletion(root, replacement);</span><br><span class="line"></span><br><span class="line">            <span class="keyword">if</span> (replacement == p) &#123;  <span class="comment">// detach</span></span><br><span class="line">                TreeNode&lt;K,V&gt; pp = p.parent;</span><br><span class="line">                p.parent = <span class="keyword">null</span>;</span><br><span class="line">                <span class="keyword">if</span> (pp != <span class="keyword">null</span>) &#123;</span><br><span class="line">                    <span class="keyword">if</span> (p == pp.left)</span><br><span class="line">                        pp.left = <span class="keyword">null</span>;</span><br><span class="line">                    <span class="keyword">else</span> <span class="keyword">if</span> (p == pp.right)</span><br><span class="line">                        pp.right = <span class="keyword">null</span>;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span> (movable)</span><br><span class="line">                moveRootToFront(tab, r);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">/**</span></span><br><span class="line"><span class="comment">         * Splits nodes in a tree bin into lower and upper tree bins,</span></span><br><span class="line"><span class="comment">         * or untreeifies if now too small. Called only from resize;</span></span><br><span class="line"><span class="comment">         * see above discussion about split bits and indices.</span></span><br><span class="line"><span class="comment">         *</span></span><br><span class="line"><span class="comment">         * <span class="doctag">@param</span> map the map</span></span><br><span class="line"><span class="comment">         * <span class="doctag">@param</span> tab the table for recording bin heads</span></span><br><span class="line"><span class="comment">         * <span class="doctag">@param</span> index the index of the table being split</span></span><br><span class="line"><span class="comment">         * <span class="doctag">@param</span> bit the bit of hash to split on</span></span><br><span class="line"><span class="comment">         */</span></span><br><span class="line">        <span class="function"><span class="keyword">final</span> <span class="keyword">void</span> <span class="title">split</span><span class="params">(HashMap&lt;K,V&gt; map, Node&lt;K,V&gt;[] tab, <span class="keyword">int</span> index, <span class="keyword">int</span> bit)</span> </span>&#123;</span><br><span class="line">            TreeNode&lt;K,V&gt; b = <span class="keyword">this</span>;</span><br><span class="line">            <span class="comment">// Relink into lo and hi lists, preserving order</span></span><br><span class="line">            TreeNode&lt;K,V&gt; loHead = <span class="keyword">null</span>, loTail = <span class="keyword">null</span>;</span><br><span class="line">            TreeNode&lt;K,V&gt; hiHead = <span class="keyword">null</span>, hiTail = <span class="keyword">null</span>;</span><br><span class="line">            <span class="keyword">int</span> lc = <span class="number">0</span>, hc = <span class="number">0</span>;</span><br><span class="line">            <span class="keyword">for</span> (TreeNode&lt;K,V&gt; e = b, next; e != <span class="keyword">null</span>; e = next) &#123;</span><br><span class="line">                next = (TreeNode&lt;K,V&gt;)e.next;</span><br><span class="line">                e.next = <span class="keyword">null</span>;</span><br><span class="line">                <span class="keyword">if</span> ((e.hash &amp; bit) == <span class="number">0</span>) &#123;</span><br><span class="line">                    <span class="keyword">if</span> ((e.prev = loTail) == <span class="keyword">null</span>)</span><br><span class="line">                        loHead = e;</span><br><span class="line">                    <span class="keyword">else</span></span><br><span class="line">                        loTail.next = e;</span><br><span class="line">                    loTail = e;</span><br><span class="line">                    ++lc;</span><br><span class="line">                &#125;</span><br><span class="line">                <span class="keyword">else</span> &#123;</span><br><span class="line">                    <span class="keyword">if</span> ((e.prev = hiTail) == <span class="keyword">null</span>)</span><br><span class="line">                        hiHead = e;</span><br><span class="line">                    <span class="keyword">else</span></span><br><span class="line">                        hiTail.next = e;</span><br><span class="line">                    hiTail = e;</span><br><span class="line">                    ++hc;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line">            <span class="keyword">if</span> (loHead != <span class="keyword">null</span>) &#123;</span><br><span class="line">                <span class="keyword">if</span> (lc &lt;= UNTREEIFY_THRESHOLD)</span><br><span class="line">                    tab[index] = loHead.untreeify(map);</span><br><span class="line">                <span class="keyword">else</span> &#123;</span><br><span class="line">                    tab[index] = loHead;</span><br><span class="line">                    <span class="keyword">if</span> (hiHead != <span class="keyword">null</span>) <span class="comment">// (else is already treeified)</span></span><br><span class="line">                        loHead.treeify(tab);</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span> (hiHead != <span class="keyword">null</span>) &#123;</span><br><span class="line">                <span class="keyword">if</span> (hc &lt;= UNTREEIFY_THRESHOLD)</span><br><span class="line">                    tab[index + bit] = hiHead.untreeify(map);</span><br><span class="line">                <span class="keyword">else</span> &#123;</span><br><span class="line">                    tab[index + bit] = hiHead;</span><br><span class="line">                    <span class="keyword">if</span> (loHead != <span class="keyword">null</span>)</span><br><span class="line">                        hiHead.treeify(tab);</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">/* ------------------------------------------------------------ */</span></span><br><span class="line">        <span class="comment">// Red-black tree methods, all adapted from CLR</span></span><br><span class="line"></span><br><span class="line">        <span class="keyword">static</span> &lt;K,V&gt; <span class="function">TreeNode&lt;K,V&gt; <span class="title">rotateLeft</span><span class="params">(TreeNode&lt;K,V&gt; root,</span></span></span><br><span class="line"><span class="function"><span class="params">                                              TreeNode&lt;K,V&gt; p)</span> </span>&#123;</span><br><span class="line">            TreeNode&lt;K,V&gt; r, pp, rl;</span><br><span class="line">            <span class="keyword">if</span> (p != <span class="keyword">null</span> &amp;&amp; (r = p.right) != <span class="keyword">null</span>) &#123;</span><br><span class="line">                <span class="keyword">if</span> ((rl = p.right = r.left) != <span class="keyword">null</span>)</span><br><span class="line">                    rl.parent = p;</span><br><span class="line">                <span class="keyword">if</span> ((pp = r.parent = p.parent) == <span class="keyword">null</span>)</span><br><span class="line">                    (root = r).red = <span class="keyword">false</span>;</span><br><span class="line">                <span class="keyword">else</span> <span class="keyword">if</span> (pp.left == p)</span><br><span class="line">                    pp.left = r;</span><br><span class="line">                <span class="keyword">else</span></span><br><span class="line">                    pp.right = r;</span><br><span class="line">                r.left = p;</span><br><span class="line">                p.parent = r;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">return</span> root;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">static</span> &lt;K,V&gt; <span class="function">TreeNode&lt;K,V&gt; <span class="title">rotateRight</span><span class="params">(TreeNode&lt;K,V&gt; root,</span></span></span><br><span class="line"><span class="function"><span class="params">                                               TreeNode&lt;K,V&gt; p)</span> </span>&#123;</span><br><span class="line">            TreeNode&lt;K,V&gt; l, pp, lr;</span><br><span class="line">            <span class="keyword">if</span> (p != <span class="keyword">null</span> &amp;&amp; (l = p.left) != <span class="keyword">null</span>) &#123;</span><br><span class="line">                <span class="keyword">if</span> ((lr = p.left = l.right) != <span class="keyword">null</span>)</span><br><span class="line">                    lr.parent = p;</span><br><span class="line">                <span class="keyword">if</span> ((pp = l.parent = p.parent) == <span class="keyword">null</span>)</span><br><span class="line">                    (root = l).red = <span class="keyword">false</span>;</span><br><span class="line">                <span class="keyword">else</span> <span class="keyword">if</span> (pp.right == p)</span><br><span class="line">                    pp.right = l;</span><br><span class="line">                <span class="keyword">else</span></span><br><span class="line">                    pp.left = l;</span><br><span class="line">                l.right = p;</span><br><span class="line">                p.parent = l;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">return</span> root;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">static</span> &lt;K,V&gt; <span class="function">TreeNode&lt;K,V&gt; <span class="title">balanceInsertion</span><span class="params">(TreeNode&lt;K,V&gt; root,</span></span></span><br><span class="line"><span class="function"><span class="params">                                                    TreeNode&lt;K,V&gt; x)</span> </span>&#123;</span><br><span class="line">            x.red = <span class="keyword">true</span>;</span><br><span class="line">            <span class="keyword">for</span> (TreeNode&lt;K,V&gt; xp, xpp, xppl, xppr;;) &#123;</span><br><span class="line">                <span class="keyword">if</span> ((xp = x.parent) == <span class="keyword">null</span>) &#123;</span><br><span class="line">                    x.red = <span class="keyword">false</span>;</span><br><span class="line">                    <span class="keyword">return</span> x;</span><br><span class="line">                &#125;</span><br><span class="line">                <span class="keyword">else</span> <span class="keyword">if</span> (!xp.red || (xpp = xp.parent) == <span class="keyword">null</span>)</span><br><span class="line">                    <span class="keyword">return</span> root;</span><br><span class="line">                <span class="keyword">if</span> (xp == (xppl = xpp.left)) &#123;</span><br><span class="line">                    <span class="keyword">if</span> ((xppr = xpp.right) != <span class="keyword">null</span> &amp;&amp; xppr.red) &#123;</span><br><span class="line">                        xppr.red = <span class="keyword">false</span>;</span><br><span class="line">                        xp.red = <span class="keyword">false</span>;</span><br><span class="line">                        xpp.red = <span class="keyword">true</span>;</span><br><span class="line">                        x = xpp;</span><br><span class="line">                    &#125;</span><br><span class="line">                    <span class="keyword">else</span> &#123;</span><br><span class="line">                        <span class="keyword">if</span> (x == xp.right) &#123;</span><br><span class="line">                            root = rotateLeft(root, x = xp);</span><br><span class="line">                            xpp = (xp = x.parent) == <span class="keyword">null</span> ? <span class="keyword">null</span> : xp.parent;</span><br><span class="line">                        &#125;</span><br><span class="line">                        <span class="keyword">if</span> (xp != <span class="keyword">null</span>) &#123;</span><br><span class="line">                            xp.red = <span class="keyword">false</span>;</span><br><span class="line">                            <span class="keyword">if</span> (xpp != <span class="keyword">null</span>) &#123;</span><br><span class="line">                                xpp.red = <span class="keyword">true</span>;</span><br><span class="line">                                root = rotateRight(root, xpp);</span><br><span class="line">                            &#125;</span><br><span class="line">                        &#125;</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">                <span class="keyword">else</span> &#123;</span><br><span class="line">                    <span class="keyword">if</span> (xppl != <span class="keyword">null</span> &amp;&amp; xppl.red) &#123;</span><br><span class="line">                        xppl.red = <span class="keyword">false</span>;</span><br><span class="line">                        xp.red = <span class="keyword">false</span>;</span><br><span class="line">                        xpp.red = <span class="keyword">true</span>;</span><br><span class="line">                        x = xpp;</span><br><span class="line">                    &#125;</span><br><span class="line">                    <span class="keyword">else</span> &#123;</span><br><span class="line">                        <span class="keyword">if</span> (x == xp.left) &#123;</span><br><span class="line">                            root = rotateRight(root, x = xp);</span><br><span class="line">                            xpp = (xp = x.parent) == <span class="keyword">null</span> ? <span class="keyword">null</span> : xp.parent;</span><br><span class="line">                        &#125;</span><br><span class="line">                        <span class="keyword">if</span> (xp != <span class="keyword">null</span>) &#123;</span><br><span class="line">                            xp.red = <span class="keyword">false</span>;</span><br><span class="line">                            <span class="keyword">if</span> (xpp != <span class="keyword">null</span>) &#123;</span><br><span class="line">                                xpp.red = <span class="keyword">true</span>;</span><br><span class="line">                                root = rotateLeft(root, xpp);</span><br><span class="line">                            &#125;</span><br><span class="line">                        &#125;</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">static</span> &lt;K,V&gt; <span class="function">TreeNode&lt;K,V&gt; <span class="title">balanceDeletion</span><span class="params">(TreeNode&lt;K,V&gt; root,</span></span></span><br><span class="line"><span class="function"><span class="params">                                                   TreeNode&lt;K,V&gt; x)</span> </span>&#123;</span><br><span class="line">            <span class="keyword">for</span> (TreeNode&lt;K,V&gt; xp, xpl, xpr;;)  &#123;</span><br><span class="line">                <span class="keyword">if</span> (x == <span class="keyword">null</span> || x == root)</span><br><span class="line">                    <span class="keyword">return</span> root;</span><br><span class="line">                <span class="keyword">else</span> <span class="keyword">if</span> ((xp = x.parent) == <span class="keyword">null</span>) &#123;</span><br><span class="line">                    x.red = <span class="keyword">false</span>;</span><br><span class="line">                    <span class="keyword">return</span> x;</span><br><span class="line">                &#125;</span><br><span class="line">                <span class="keyword">else</span> <span class="keyword">if</span> (x.red) &#123;</span><br><span class="line">                    x.red = <span class="keyword">false</span>;</span><br><span class="line">                    <span class="keyword">return</span> root;</span><br><span class="line">                &#125;</span><br><span class="line">                <span class="keyword">else</span> <span class="keyword">if</span> ((xpl = xp.left) == x) &#123;</span><br><span class="line">                    <span class="keyword">if</span> ((xpr = xp.right) != <span class="keyword">null</span> &amp;&amp; xpr.red) &#123;</span><br><span class="line">                        xpr.red = <span class="keyword">false</span>;</span><br><span class="line">                        xp.red = <span class="keyword">true</span>;</span><br><span class="line">                        root = rotateLeft(root, xp);</span><br><span class="line">                        xpr = (xp = x.parent) == <span class="keyword">null</span> ? <span class="keyword">null</span> : xp.right;</span><br><span class="line">                    &#125;</span><br><span class="line">                    <span class="keyword">if</span> (xpr == <span class="keyword">null</span>)</span><br><span class="line">                        x = xp;</span><br><span class="line">                    <span class="keyword">else</span> &#123;</span><br><span class="line">                        TreeNode&lt;K,V&gt; sl = xpr.left, sr = xpr.right;</span><br><span class="line">                        <span class="keyword">if</span> ((sr == <span class="keyword">null</span> || !sr.red) &amp;&amp;</span><br><span class="line">                            (sl == <span class="keyword">null</span> || !sl.red)) &#123;</span><br><span class="line">                            xpr.red = <span class="keyword">true</span>;</span><br><span class="line">                            x = xp;</span><br><span class="line">                        &#125;</span><br><span class="line">                        <span class="keyword">else</span> &#123;</span><br><span class="line">                            <span class="keyword">if</span> (sr == <span class="keyword">null</span> || !sr.red) &#123;</span><br><span class="line">                                <span class="keyword">if</span> (sl != <span class="keyword">null</span>)</span><br><span class="line">                                    sl.red = <span class="keyword">false</span>;</span><br><span class="line">                                xpr.red = <span class="keyword">true</span>;</span><br><span class="line">                                root = rotateRight(root, xpr);</span><br><span class="line">                                xpr = (xp = x.parent) == <span class="keyword">null</span> ?</span><br><span class="line">                                    <span class="keyword">null</span> : xp.right;</span><br><span class="line">                            &#125;</span><br><span class="line">                            <span class="keyword">if</span> (xpr != <span class="keyword">null</span>) &#123;</span><br><span class="line">                                xpr.red = (xp == <span class="keyword">null</span>) ? <span class="keyword">false</span> : xp.red;</span><br><span class="line">                                <span class="keyword">if</span> ((sr = xpr.right) != <span class="keyword">null</span>)</span><br><span class="line">                                    sr.red = <span class="keyword">false</span>;</span><br><span class="line">                            &#125;</span><br><span class="line">                            <span class="keyword">if</span> (xp != <span class="keyword">null</span>) &#123;</span><br><span class="line">                                xp.red = <span class="keyword">false</span>;</span><br><span class="line">                                root = rotateLeft(root, xp);</span><br><span class="line">                            &#125;</span><br><span class="line">                            x = root;</span><br><span class="line">                        &#125;</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">                <span class="keyword">else</span> &#123; <span class="comment">// symmetric</span></span><br><span class="line">                    <span class="keyword">if</span> (xpl != <span class="keyword">null</span> &amp;&amp; xpl.red) &#123;</span><br><span class="line">                        xpl.red = <span class="keyword">false</span>;</span><br><span class="line">                        xp.red = <span class="keyword">true</span>;</span><br><span class="line">                        root = rotateRight(root, xp);</span><br><span class="line">                        xpl = (xp = x.parent) == <span class="keyword">null</span> ? <span class="keyword">null</span> : xp.left;</span><br><span class="line">                    &#125;</span><br><span class="line">                    <span class="keyword">if</span> (xpl == <span class="keyword">null</span>)</span><br><span class="line">                        x = xp;</span><br><span class="line">                    <span class="keyword">else</span> &#123;</span><br><span class="line">                        TreeNode&lt;K,V&gt; sl = xpl.left, sr = xpl.right;</span><br><span class="line">                        <span class="keyword">if</span> ((sl == <span class="keyword">null</span> || !sl.red) &amp;&amp;</span><br><span class="line">                            (sr == <span class="keyword">null</span> || !sr.red)) &#123;</span><br><span class="line">                            xpl.red = <span class="keyword">true</span>;</span><br><span class="line">                            x = xp;</span><br><span class="line">                        &#125;</span><br><span class="line">                        <span class="keyword">else</span> &#123;</span><br><span class="line">                            <span class="keyword">if</span> (sl == <span class="keyword">null</span> || !sl.red) &#123;</span><br><span class="line">                                <span class="keyword">if</span> (sr != <span class="keyword">null</span>)</span><br><span class="line">                                    sr.red = <span class="keyword">false</span>;</span><br><span class="line">                                xpl.red = <span class="keyword">true</span>;</span><br><span class="line">                                root = rotateLeft(root, xpl);</span><br><span class="line">                                xpl = (xp = x.parent) == <span class="keyword">null</span> ?</span><br><span class="line">                                    <span class="keyword">null</span> : xp.left;</span><br><span class="line">                            &#125;</span><br><span class="line">                            <span class="keyword">if</span> (xpl != <span class="keyword">null</span>) &#123;</span><br><span class="line">                                xpl.red = (xp == <span class="keyword">null</span>) ? <span class="keyword">false</span> : xp.red;</span><br><span class="line">                                <span class="keyword">if</span> ((sl = xpl.left) != <span class="keyword">null</span>)</span><br><span class="line">                                    sl.red = <span class="keyword">false</span>;</span><br><span class="line">                            &#125;</span><br><span class="line">                            <span class="keyword">if</span> (xp != <span class="keyword">null</span>) &#123;</span><br><span class="line">                                xp.red = <span class="keyword">false</span>;</span><br><span class="line">                                root = rotateRight(root, xp);</span><br><span class="line">                            &#125;</span><br><span class="line">                            x = root;</span><br><span class="line">                        &#125;</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">/**</span></span><br><span class="line"><span class="comment">         * Recursive invariant check</span></span><br><span class="line"><span class="comment">         */</span></span><br><span class="line">        <span class="keyword">static</span> &lt;K,V&gt; <span class="function"><span class="keyword">boolean</span> <span class="title">checkInvariants</span><span class="params">(TreeNode&lt;K,V&gt; t)</span> </span>&#123;</span><br><span class="line">            TreeNode&lt;K,V&gt; tp = t.parent, tl = t.left, tr = t.right,</span><br><span class="line">                tb = t.prev, tn = (TreeNode&lt;K,V&gt;)t.next;</span><br><span class="line">            <span class="keyword">if</span> (tb != <span class="keyword">null</span> &amp;&amp; tb.next != t)</span><br><span class="line">                <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">            <span class="keyword">if</span> (tn != <span class="keyword">null</span> &amp;&amp; tn.prev != t)</span><br><span class="line">                <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">            <span class="keyword">if</span> (tp != <span class="keyword">null</span> &amp;&amp; t != tp.left &amp;&amp; t != tp.right)</span><br><span class="line">                <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">            <span class="keyword">if</span> (tl != <span class="keyword">null</span> &amp;&amp; (tl.parent != t || tl.hash &gt; t.hash))</span><br><span class="line">                <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">            <span class="keyword">if</span> (tr != <span class="keyword">null</span> &amp;&amp; (tr.parent != t || tr.hash &lt; t.hash))</span><br><span class="line">                <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">            <span class="keyword">if</span> (t.red &amp;&amp; tl != <span class="keyword">null</span> &amp;&amp; tl.red &amp;&amp; tr != <span class="keyword">null</span> &amp;&amp; tr.red)</span><br><span class="line">                <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">            <span class="keyword">if</span> (tl != <span class="keyword">null</span> &amp;&amp; !checkInvariants(tl))</span><br><span class="line">                <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">            <span class="keyword">if</span> (tr != <span class="keyword">null</span> &amp;&amp; !checkInvariants(tr))</span><br><span class="line">                <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>

</article><div class="post-copyright"><div class="post-copyright__author"><span class="post-copyright-meta">文章作者: </span><span class="post-copyright-info"><a href="mailto:undefined">方陈勇</a></span></div><div class="post-copyright__type"><span class="post-copyright-meta">文章链接: </span><span class="post-copyright-info"><a href="https://fangchenyong.top/2021/03/20/Java-%E6%BA%90%E7%A0%81-JDK8-HashMap/">https://fangchenyong.top/2021/03/20/Java-%E6%BA%90%E7%A0%81-JDK8-HashMap/</a></span></div><div class="post-copyright__notice"><span class="post-copyright-meta">版权声明: </span><span class="post-copyright-info">本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" target="_blank">CC BY-NC-SA 4.0</a> 许可协议。转载请注明来自 <a href="https://fangchenyong.top" target="_blank">Joey</a>！</span></div></div><div class="tag_share"><div class="post-meta__tag-list"><a class="post-meta__tags" href="/tags/Java/">Java</a><a class="post-meta__tags" href="/tags/%E6%BA%90%E7%A0%81/">源码</a><a class="post-meta__tags" href="/tags/HashMap/">HashMap</a></div><div class="post_share"><div class="social-share" data-image="https://fangchenyong.oss-cn-hangzhou.aliyuncs.com/BEF238F4E59CF4D91A694FE9C5DBC030.JPG" data-sites="facebook,twitter,wechat,weibo,qq"></div><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/social-share.js/dist/css/share.min.css" media="print" onload="this.media='all'"><script src="https://cdn.jsdelivr.net/npm/social-share.js/dist/js/social-share.min.js" defer></script></div></div><nav class="pagination-post" id="pagination"><div class="prev-post pull-left"><a href="/2021/03/20/%E9%9D%A2%E8%AF%95-%E9%9B%86%E5%90%88/"><img class="prev-cover" src="https://fangchenyong.oss-cn-hangzhou.aliyuncs.com/BEF238F4E59CF4D91A694FE9C5DBC030.JPG" onerror="onerror=null;src='/img/404.jpg'" alt="cover of previous post"><div class="pagination-info"><div class="label">上一篇</div><div class="prev_info">面试题-集合框架</div></div></a></div><div class="next-post pull-right"><a href="/2021/03/13/The%20Road%20To%20Bald%20Man!/"><img class="next-cover" src="https://fangchenyong.oss-cn-hangzhou.aliyuncs.com/BEF238F4E59CF4D91A694FE9C5DBC030.JPG" onerror="onerror=null;src='/img/404.jpg'" alt="cover of next post"><div class="pagination-info"><div class="label">下一篇</div><div class="next_info">The Road To Bald Man!</div></div></a></div></nav><div class="relatedPosts"><div class="headline"><i class="fas fa-thumbs-up fa-fw"></i><span> 相关推荐</span></div><div class="relatedPosts-list"><div><a href="/2019/09/06/Java-源码-JDK8-String/" title="JDK8 String源码"><img class="cover" src="https://fangchenyong.oss-cn-hangzhou.aliyuncs.com/BEF238F4E59CF4D91A694FE9C5DBC030.JPG" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2019-09-06</div><div class="title">JDK8 String源码</div></div></a></div><div><a href="/2019/08/23/Java-源码-JDK8-Object/" title="JDK8 Object源码"><img class="cover" src="https://fangchenyong.oss-cn-hangzhou.aliyuncs.com/BEF238F4E59CF4D91A694FE9C5DBC030.JPG" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2019-08-23</div><div class="title">JDK8 Object源码</div></div></a></div><div><a href="/2021/04/12/Java-深入理解Java虚拟机/" title="深入理解Java虚拟机"><img class="cover" src="https://fangchenyong.oss-cn-hangzhou.aliyuncs.com/BEF238F4E59CF4D91A694FE9C5DBC030.JPG" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2021-04-12</div><div class="title">深入理解Java虚拟机</div></div></a></div><div><a href="/2019/08/23/项目-基于Netty+WebSocket简易版微信/" title="基于Netty+WebSocket简易版微信"><img class="cover" src="https://fangchenyong.oss-cn-hangzhou.aliyuncs.com/BEF238F4E59CF4D91A694FE9C5DBC030.JPG" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2019-08-23</div><div class="title">基于Netty+WebSocket简易版微信</div></div></a></div><div><a href="/2019/07/29/项目-理财产品系统/" title="理财产品系统（慕课网）"><img class="cover" src="https://fangchenyong.oss-cn-hangzhou.aliyuncs.com/BEF238F4E59CF4D91A694FE9C5DBC030.JPG" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2019-07-29</div><div class="title">理财产品系统（慕课网）</div></div></a></div><div><a href="/2019/07/20/Java-Java基础笔记/" title="Java基础笔记"><img class="cover" src="https://fangchenyong.oss-cn-hangzhou.aliyuncs.com/BEF238F4E59CF4D91A694FE9C5DBC030.JPG" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2019-07-20</div><div class="title">Java基础笔记</div></div></a></div></div></div></div><div class="aside-content" id="aside-content"><div class="card-widget card-info"><div class="card-info-avatar is-center"><img class="avatar-img" src="https://fangchenyong.oss-cn-hangzhou.aliyuncs.com/3FD9B055-6361-49B7-B8CE-5BA9144BD27F.JPG" onerror="this.onerror=null;this.src='/img/friend_404.gif'" alt="avatar"/><div class="author-info__name">方陈勇</div><div class="author-info__description">一路向前</div></div><div class="card-info-data"><div class="card-info-data-item is-center"><a href="/archives/"><div class="headline">文章</div><div class="length-num">43</div></a></div><div class="card-info-data-item is-center"><a href="/tags/"><div class="headline">标签</div><div class="length-num">51</div></a></div><div class="card-info-data-item is-center"><a href="/categories/"><div class="headline">分类</div><div class="length-num">53</div></a></div></div><a class="button--animated" id="card-info-btn" target="_blank" rel="noopener" href="https://github.com/fangchenyong"><i class="fab fa-github"></i><span>Follow Me</span></a><div class="card-info-social-icons is-center"><a class="social-icon" href="https://github.com/fangchenyong" target="_blank" title="Github"><i class="fab fa-github"></i></a><a class="social-icon" href="mailto:1013659102@qq.com" target="_blank" title="Email"><i class="fas fa-envelope"></i></a></div></div><div class="card-widget card-announcement"><div class="item-headline"><i class="fas fa-bullhorn card-announcement-animation"></i><span>公告</span></div><div class="announcement_content">个人笔记，如有疑问请联系 QQ:1013659102。</div></div><div class="sticky_layout"><div class="card-widget" id="card-toc"><div class="item-headline"><i class="fas fa-stream"></i><span>目录</span></div><div class="toc-content"><ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#HashMap%E6%BA%90%E7%A0%81"><span class="toc-number">1.</span> <span class="toc-text">HashMap源码</span></a></li></ol></div></div><div class="card-widget card-recent-post"><div class="item-headline"><i class="fas fa-history"></i><span>最新文章</span></div><div class="aside-list"><div class="aside-list-item"><a class="thumbnail" href="/2021/05/06/%E7%AE%97%E6%B3%95-%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F/" title="算法"><img src="https://fangchenyong.oss-cn-hangzhou.aliyuncs.com/BEF238F4E59CF4D91A694FE9C5DBC030.JPG" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="算法"/></a><div class="content"><a class="title" href="/2021/05/06/%E7%AE%97%E6%B3%95-%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F/" title="算法">算法</a><time datetime="2021-05-05T16:00:00.000Z" title="发表于 2021-05-06 00:00:00">2021-05-06</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/2021/05/06/%E7%AE%97%E6%B3%95-%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F/" title="选择排序"><img src="https://fangchenyong.oss-cn-hangzhou.aliyuncs.com/BEF238F4E59CF4D91A694FE9C5DBC030.JPG" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="选择排序"/></a><div class="content"><a class="title" href="/2021/05/06/%E7%AE%97%E6%B3%95-%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F/" title="选择排序">选择排序</a><time datetime="2021-05-05T16:00:00.000Z" title="发表于 2021-05-06 00:00:00">2021-05-06</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/2021/04/12/Java-%E6%B7%B1%E5%85%A5%E7%90%86%E8%A7%A3Java%E8%99%9A%E6%8B%9F%E6%9C%BA/" title="深入理解Java虚拟机"><img src="https://fangchenyong.oss-cn-hangzhou.aliyuncs.com/BEF238F4E59CF4D91A694FE9C5DBC030.JPG" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="深入理解Java虚拟机"/></a><div class="content"><a class="title" href="/2021/04/12/Java-%E6%B7%B1%E5%85%A5%E7%90%86%E8%A7%A3Java%E8%99%9A%E6%8B%9F%E6%9C%BA/" title="深入理解Java虚拟机">深入理解Java虚拟机</a><time datetime="2021-04-11T16:00:00.000Z" title="发表于 2021-04-12 00:00:00">2021-04-12</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/2021/03/21/%E9%9D%A2%E8%AF%95-%E5%B9%B6%E5%8F%91%E3%80%81%E5%A4%9A%E7%BA%BF%E7%A8%8B/" title="面试题-并发编程"><img src="https://fangchenyong.oss-cn-hangzhou.aliyuncs.com/BEF238F4E59CF4D91A694FE9C5DBC030.JPG" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="面试题-并发编程"/></a><div class="content"><a class="title" href="/2021/03/21/%E9%9D%A2%E8%AF%95-%E5%B9%B6%E5%8F%91%E3%80%81%E5%A4%9A%E7%BA%BF%E7%A8%8B/" title="面试题-并发编程">面试题-并发编程</a><time datetime="2021-03-20T16:00:00.000Z" title="发表于 2021-03-21 00:00:00">2021-03-21</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/2021/03/20/%E9%9D%A2%E8%AF%95-%E9%9B%86%E5%90%88/" title="面试题-集合框架"><img src="https://fangchenyong.oss-cn-hangzhou.aliyuncs.com/BEF238F4E59CF4D91A694FE9C5DBC030.JPG" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="面试题-集合框架"/></a><div class="content"><a class="title" href="/2021/03/20/%E9%9D%A2%E8%AF%95-%E9%9B%86%E5%90%88/" title="面试题-集合框架">面试题-集合框架</a><time datetime="2021-03-19T16:00:00.000Z" title="发表于 2021-03-20 00:00:00">2021-03-20</time></div></div></div></div></div></div></main><footer id="footer" style="background-image: url('https://fangchenyong.oss-cn-hangzhou.aliyuncs.com/BEF238F4E59CF4D91A694FE9C5DBC030.JPG')"><div id="footer-wrap"><div class="copyright">&copy;2019 - 2021 By 方陈勇</div><div class="framework-info"><span>框架 </span><a target="_blank" rel="noopener" href="https://hexo.io">Hexo</a><span class="footer-separator">|</span><span>主题 </span><a target="_blank" rel="noopener" href="https://github.com/jerryc127/hexo-theme-butterfly">Butterfly</a></div><div class="footer_custom_text">人生没有退路！</div></div></footer></div><div id="rightside"><div id="rightside-config-hide"><button id="readmode" type="button" title="阅读模式"><i class="fas fa-book-open"></i></button><button id="darkmode" type="button" title="浅色和深色模式转换"><i class="fas fa-adjust"></i></button><button id="hide-aside-btn" type="button" title="单栏和双栏切换"><i class="fas fa-arrows-alt-h"></i></button></div><div id="rightside-config-show"><button id="rightside_config" type="button" title="设置"><i class="fas fa-cog fa-spin"></i></button><button class="close" id="mobile-toc-button" type="button" title="目录"><i class="fas fa-list-ul"></i></button><button id="go-up" type="button" title="回到顶部"><i class="fas fa-arrow-up"></i></button></div></div><div><script src="/js/utils.js"></script><script src="/js/main.js"></script><div class="js-pjax"></div><script id="canvas_nest" defer="defer" color="0,0,255" opacity="0.7" zIndex="-1" count="99" mobile="false" src="https://cdn.jsdelivr.net/npm/butterfly-extsrc@1/dist/canvas-nest.min.js"></script></div></body></html>